題目:https://www.smartoj.com/p/1286

分析:花瓶是有序的，花也是有序的，這就保證了有序性，從而滿足子解的全局最優(yōu)，和無后效性.假設(shè)dp[i][j]表示前i

朵花，放在前j個花瓶里的最優(yōu)值.

則有:?

那么經(jīng)過優(yōu)化后得到:

#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\n",dp[F][V]);Print(F,V);puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的DP之花店橱窗布置的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。