首先想到一个朴素的DP：
　　将1~f-1号花摆放在1~v-1号瓶子中，而将f号花放在v号瓶子中产生的最大美观值：
saev[f,v]=max\{saev[f-1,j]+aev[f,v]~|~f-1\leq j<v\} aev[f,v]是f号花在v号瓶子中的美观值。
　　这个DP的复杂度高达O(n^3)，无法承受n=100。
　　上面的状态设定不是最大子问题，应该这样设定：
　　saev[f,v]表示将1~f号花摆放在1~v号瓶子中产生的最大美观值。
saev[f,v]=max\{saev[f-1,v-1]+aev[f,v],~saev[f,v-1]\}
　　这个是IOI的一道题，在《奥赛经典·信息学竞赛教程·提高篇》有非常详细的讲解。
　　WA on 2: 初值赋错了saev[0][0]=0 -> for (int i=0;i<=f;++i) saev[0][i]=0。
　　WA on 2: 边界没给：saev[i][j]<saev[i][j-1] 这个地方，当j=i时，没有给边界，加上一句saev[i][i-1]=-32767。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

//AC
#include <iostream>
using namespace std;
 
const int maxf=100,maxv=100;
int saev[maxf+1][maxv+1],aev[maxf+1][maxv+1];
bool put[maxf+1][maxv+1];
int f,v;
 
void printput(int i,int j)
{
    while (put[i][j]) --j;
    if (i>1) printput(i-1,j-1);
    if (i==f)
        cout<<j<<endl;
    else
        cout<<j<<' ';
}
 
int main()
{
    cin>>f>>v;
    for (int i=1;i<=f;++i)
        for (int j=1;j<=v;++j)
            cin>>aev[i][j];
    for (int i=0;i<=f;++i) saev[0][i]=0;
    for (int i=1;i<=f;++i)
    {
        saev[i][i-1]=-32767;
        for (int j=i;j<=v-f+i;++j)
        {
            saev[i][j]=saev[i-1][j-1]+aev[i][j]; put[i][j]=false;
            if (saev[i][j]<saev[i][j-1])
            {
                saev[i][j]=saev[i][j-1]; put[i][j]=true;
            }
        }
    }
    cout<<saev[f][v]<<endl;
    printput(f,v);
    return 0;
}