解题：POI 2009 Ticket Inspector

题面

看起来很水，然而不会DP的蒟蒻并不会做，PoPoqqq orz

设$f[i][j]$表示当前在第$i$个点和第$i+1$个点之间查票，已经查了$j$次的最大收益。然后就是那种很常见的枚举前一个结尾的转移，主要是贡献的求法，从$x$到$y$的贡献是$val[(x+1,y+1)][(y,n)]$(二维前缀和一下)。对于方案就在更新时记录上一个结尾即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=605,K=60;
int fsum[N][N],dp[N][K],las[N][K],outp[K];
int n,k,ans,cnt,pos;
int main ()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            scanf("%d",&fsum[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fsum[i][j]+=fsum[i-1][j]+fsum[i][j-1]-fsum[i-1][j-1];
    memset(dp,0xcf,sizeof dp),dp[0][0]=0;
    for(int i=1;i<n;i++)
        for(int j=1;j<=k;j++)
            for(int h=0;h<i;h++)
            {
                int tmp=fsum[i][n]-fsum[h][n]-fsum[i][i]+fsum[h][i];
                if(dp[h][j-1]+tmp>dp[i][j]) {dp[i][j]=dp[h][j-1]+tmp; las[i][j]=h;}
            }
    for(int i=1;i<n;i++) 
        if(dp[i][k]>ans) ans=dp[i][k],pos=i;
    while(k) outp[++cnt]=pos,pos=las[pos][k--];
    sort(outp+1,outp+1+cnt);
    for(int i=1;i<=cnt;i++) 
        printf("%d ",outp[i]);
    return 0;
}