题目
?id=1157
题目大意
有f个花,k个瓶子,每个花放每个瓶子都有一个特定的美学值,问美学值最大是多少.注意,i号花不能出现在某大于i号花后面.问最大美学值是多少
解题思路
dp[i][j]表示将第i个花插入第k个瓶子的最大美学值. 状态转移方程为dp[i][j] = max(dp[i-1][(i-1)~(k-f+i-1)]) + value[i][j]
代码#include <cstdio>const int maxn = 110;int f,k;int v[maxn][maxn];int dp[maxn][maxn];int main(){scanf(“%d%d”,&f,&k);for(int i = 1 ; i <= f ; i ++) {for(int j = 1 ; j <= k ; j ++) scanf(“%d”,&v[i][j]);}for(int i = 1 ; i <= k-f+1 ; i ++) dp[1][i] = v[1][i];//dpfor(int i = 2; i <= f ; i ++) {for(int j = i ; j <= k-f+i ; j ++) {int ma = -100000000;for(int kk = i-1 ; kk < j ; kk ++) {if(ma < dp[i-1][kk]) ma = dp[i-1][kk];}dp[i][j] = ma+v[i][j];}}int ma = -10000000;for(int i = f ; i <= k ; i ++) if(ma < dp[f][i]) ma = dp[f][i];printf(“%d\n”,ma);return 0;}
，生命不息，在任何一种博大的辉煌之后，都掩藏着许多鲜为人知的艰难的奋斗。
