花店橱窗（动态规划）

这题符合动态规划的条件，即在每选一盆花时，选这盆花的操作不受上次选择的干扰，每一次维护数组时，都维护出了选第i盆花时的最优解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int f,v;
int mp[200][200];
int dp[200][200];
int main(){
    cin>>f>>v;
    for(int x=1; x<=f; x++){
        for(int y=1; y<=v; y++){
            cin>>mp[x][y];
        }
    }
    memset(dp,-0x3f3f3f3f,sizeof(dp));
    for (int i = 1; i <=v; ++ i) 
        dp[1][i] = mp[1][i];
    for(int i=2; i<=f; i++){
        for(int j=1; j<=v; j++){
            for(int k=1; k<j; k++)
                dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[i][j]);
        }
    }
    int sum=-0x3f3f3f3f;
    for(int i=1; i<=v; i++)
        //cout<<dp[3][i]<<" ";
       sum=max(sum,dp[f][i]);
       cout<<sum<<endl;
        
    int res[200];
    for(int y=f; y>=1; y--){
        for(int x=v; x>=1; x--){
            if(dp[y][x]==sum)
            {res[y]=x;}
        }
        sum=sum-mp[y][res[y]];
    }
    for(int i=1; i<=f; i++)
        cout<<res[i]<<" ";
    return 0;
}

注意每一次并不是拿上次的最优解来加上当前盆的值，这样的贪心策略是错误的，因为这一次的贡献可能比上次更多。