题解 | #花店橱窗#

一、考虑状态转移方程怎么写：

1、首先考虑子问题是怎么样的，原问题是求把编号为1~ f的花束，随机放进1~v这v个瓶子里面，且需要按照编号顺序放置，每个花瓶只能放一朵花，的最美观方案。

子问题就可以是，把编号为1~ i的花束，随机放进1~j这j个瓶子里面的最美观方案。显然子问题和原问题的求解方法是一样的，子问题假设正确。

2、接着分析后效性，首先构造一个一维dp数组，dp[M]，描述第M朵花放置在第i个花瓶时的最美观方案，当前状态的选择一定会影响后一个状态的决策，这个状态选了一个数值，为了保证得到最美观方案，下一个状态还需要讨论选哪个数值更好，很复杂，不符合动态规划的本意。

消除后效性

增加一个维度，变为dp[M][M]，表示前i多花按顺序任意放置在前j个花瓶中的最美观方案。

#include<bits/stdc++.h>
using namespace std;
int f,v;
const int M=105;
int a[M][M];    //第几种花 第几个花瓶
int dp[M][M];
void printmax(int maxn,int i,int j){
    if(i==0) return ;
    for(int k=1;k<=v;k++){
        if(dp[i-1][k]+a[i][j]==maxn){
            printmax(dp[i-1][k],i-1,k);
            break;
        }
    }
    cout<<j<<" ";
}
int main(){
    cin>>f>>v;
    for(int i=1;i<=f;i++){
        for(int j=1;j<=v;j++){
            cin>>a[i][j];
            dp[i][j]=-10000;
        }
    }
    for(int i=1;i<=v;i++) dp[1][i]=a[1][i];
    for(int i=1;i<=f;i++){
        for(int j=i;j<=v-(f-i);j++){
            for(int k=i-1;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
            }
        }
    }
    int pos=0;
	int ans=-1e8;
	for(int i=f;i<=v;i++){
		if(ans<dp[f][i]){
            ans=dp[f][i];
            pos=i;
        }
	}
	cout<<ans<<endl;
    printmax(ans,f,pos);
	return 0;
}