花店橱窗

题目大意：给定 种花 个花瓶，每种花插在花瓶上都有一个美观值 ,对于第 种花，满足第 种花插在的花瓶位置一定是在第 种花插在花瓶位置之前.每个花瓶只能插一种花。问将 朵花插入花瓶最大的美观值之和是多少.并且输出插入花瓶的位置方案。(如果有方案美观值相同，按字典序最小输出)

分析：动态规划.

• 表示第 种花插入第 个花瓶、前 种花插入前 个花瓶的最大美观值。
• 转移方程： .
  可以用前缀和维护。
• 最优解方案可以用 表示当前 前 种花插入前 个花瓶中可以获得最大的美观值，第 种花插入的花瓶位置。
  因为是字典序最小所以转移时
  
• 就是最大美观值，获得方案，需要倒序遍历找到最优位置，然后倒置输出。

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#define mk make_pair
#define pb push_back
using namespace std;

typedef long long ll;

int a[105][105];
ll dp[105][105];
int pos[105][105];

int main()
{
    int n,m;
    cin>>n>>m;
    for( int i=1;i<=n;i++ )
    {
        dp[i][i-1]=-1e10;
        for( int j=1;j<=m;j++ )    cin>>a[i][j];
        for( int j=i;j<=m;j++ )    dp[i][j]=dp[i-1][j-1]+a[i][j];
        for( int j=i;j<=m;j++ ) 
        {
            if( dp[i][j-1]>=dp[i][j] ) pos[i][j]=pos[i][j-1];
            else pos[i][j]=j;
            dp[i][j]=max(dp[i][j-1],dp[i][j]);
        }

    }
    int now=m;
    cout<<dp[n][m]<<endl;
    vector<int> ans;
    for( int i=n;i>=1;i-- )
    {
        ans.push_back(pos[i][now]);
        now=pos[i][now]-1;
    }
    reverse(ans.begin(),ans.end());
    for( auto v: ans )
     cout<<v<<" ";

}