题目: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\n",dp[F][V]);

        Print(F,V);

        puts("");

    }

    return 0;

}