CH5E02 [IOI1999]花店橱窗[暴力dp]

众所周知，这个人太菜了，所以她又来切水题了。

显然设计状态表示第$i$朵花放第$j$瓶中的最大价值。然后瞎转移一波是n三方的，加个前缀max变成n方就水过去了。

当然这题可以搜索剪枝的。

虐lyd书上水题好爽。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define _dbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
const int N=100+7,INF=0x7f7f7f7f;
int f[N][N],a[N][N],maxv[N][N];
int n,m,ans,x;
void print(int i,int j){
    if(!i)return;
    print(i-1,maxv[i-1][j-1]);
    printf("%d ",j);
}

int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
    read(n),read(m);
    for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)read(a[i][j]);
    for(register int i=1;i<=n;++i){
        int tmp=-INF;
        for(register int j=i;j<=m;++j){
            f[i][j]=a[i][j]+f[i-1][maxv[i-1][j-1]];
            maxv[i][j]=MAX(tmp,f[i][j])?j:maxv[i][j-1];
        }
    }
    for(register int i=n;i<=m;++i)if(MAX(ans,f[n][i]))x=i;
    printf("%d
",ans);
    print(n,x);puts("");
    return 0;
}