DP之花店橱窗布置 - c++编程基础

分析:花瓶是有序的，花也是有序的，这就保证了有序性，从而满足子解的全局最优，和无后效性.假设dp[i][j]表示前i

朵花，放在前j个花瓶里的最优值.

则有:

那么经过优化后得到:

#include   
#include   
#include   
  
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;  
}