摘要：
你们好啊，我又回来了。P1854这是一道动态规划题。我这里介绍一下这题正解-˃dp。其实很显然的吧........这个题，我们考虑我们考虑用f[i][j]f[i][j]来表示第i束花插在第j个花瓶里时的最优解。故而可以推出dp[i][j]=max+a[i][j];所以不就是几个循环的事吗逃】放完整代码（已AC）有极少注释#include#include#include#include#includeusingnamespacestd;intf,v,ans;intz[101][101],g[101][101],b[101][101];//表示，前i的花放在前j的瓶；在g中i-1的位置intd[101];intmain(){scanf;forforscanf;forg[1][i]=z[1][i];forfor//第j个for//第i-1束花的位置if{g[i][j]=g[i-1][k]+z[i][j];b[i][j]=k;//等候i-1}intsum=0,max=-2147483647;for{if{max=g[f][i];sum=i;}}cout˂˂max˂˂endl;for{d[i]=sum;sum=b[f-i+1][sum];}forcout˂˂d[i]˂˂endl;return0;}变量名过丑，请自行脑补。
你们好啊，我又回来了。P1854这是一道动态规划题。
还是先放题目，防止走错》》》
这次先放数据，上次就忘了..........
其实我们看见数据只有100，其实就可以考虑瞎搞，什么记忆化搜索，题解还有人求最长路，闲的无聊你可以自己尝试。
我这里介绍一下这题正解 -> dp。
其实很显然的吧........
这个题，我们考虑我们考虑用f[i][j]f[i][j]来表示第i束花插在第j个花瓶里时的最优解（即最大的美学值）。
故而可以推出dp[i][j]=max(dp[i-1][1],dp[i-1][2], ........ ,dp[i-1][j-1])+a[i][j];
所以不就是几个循环的事吗 逃】
放完整代码（已AC）有极少注释
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath> using namespacestd; intf,v,ans; int z[101][101],g[101][101],b[101][101]; //表示，前i的花放在前j的瓶；在 g中i-1的位置 int d[101]; intmain() { scanf("%d%d",&f,&v); for(int i=1;i<=f;i++) for(int j=1;j<=v;j++) scanf("%d",&z[i][j]); for(int i=1;i<=v-f+1;i++) g[1][i]=z[1][i]; for(int i=2;i<=f;i++) for(int j=i;j<=v-f+i;j++)//第j个 for(int k=i-1;k<=j-1;k++)//第i-1束花的位置 if(g[i-1][k]+z[i][j]>g[i][j]) { g[i][j]=g[i-1][k]+z[i][j]; b[i][j]=k;//等候i-1 } int sum=0,max=-2147483647; for(int i=f;i<=v;i++) { if(g[f][i]>max) { max=g[f][i]; sum=i; } } cout<<max<<endl; for(int i=1;i<=f;i++) { d[i]=sum; sum=b[f-i+1][sum]; } for(int i=f;i>=1;i--) cout<<d[i]<<endl; return 0; }
变量名过丑，请自行脑补。
谢谢观看。