你们好啊，我又回来了。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 namespace std; int f,v,ans; int z[101][101],g[101][101],b[101][101]; //表示，前i的花放在前j的瓶；在 g中i-1的位置 int d[101]; int main() { 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; }
变量名过丑，请自行脑补。
谢谢观看。
原文：https://www.cnblogs.com/qxyzili--24/p/10425901.html