题目:https://www.smartoj.com/p/1286
分析:花瓶是有序的,花也是有序的,这就保证了有序性,从而满足子解的全局最优,和无后效性.假设dp[i][j]表示前i
朵花,放在前j个花瓶里的最优值.
则有:
那么经过优化后得到:
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N = 105; const int INF = 1<<30; int a[N][N]; int dp[N][N]; bool path[N][N]; void Print(int i,int j) { if(i == 0) return; if(path[i][j]) { Print(i-1,j-1); printf("%d ",j); } else Print(i,j-1); } int main() { int F,V; while(~scanf("%d%d",&F,&V)) { memset(path,0,sizeof(path)); for(int i=1;i<=F;i++) for(int j=1;j<=V;j++) scanf("%d",&a[i][j]); for(int i=1;i<=F;i++) for(int j=0;j<=V;j++) dp[i][j] = -INF; for(int i=1;i<=F;i++) { for(int j=i;j<=V && i <= i + F;j++) { if(dp[i-1][j-1] + a[i][j] <= dp[i][j-1]) dp[i][j] = dp[i][j-1]; else { dp[i][j] = dp[i-1][j-1] + a[i][j]; path[i][j] = 1; } } } printf("%d ",dp[F][V]); Print(F,V); puts(""); } return 0; }