bzoj1133: [POI2009]Kon

链接

思路

f[i][k]表示前i个，选了k个，其中必选i的最大值

f[i][k]=f[j][k-1]+贡献

这个贡献就是j到i之间的边界碰到i的人数(可以预处理个前缀和)

复杂度O(nnk)

错误

貌似输出方案错了还是神马的,90分

不过bzoj数据都过了呀，bzoj还会改数据吗

错误代码

#include 
    
     using namespace std;const int N=607,M=57;int read() {    int x=0,f=1;char s=getchar();    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';    return x*f;}int n,K,f[N][M],sum[N][N],frm[N][M];int stak[N],top;int main() {    n=read(),K=read();    for(int i=1;i<=n;++i)        for(int j=i+1;j<=n;++j)            sum[i][j]=sum[i][j-1]+read();    for(int k=1;k<=K;++k) for(int i=1;i<=n;++i){        int tot=0;        for(int j=i;j>=1;--j) {            tot+=sum[j][n]-sum[j][i];            if(f[i][k]==f[j-1][k-1]+tot) frm[i][k]=min(frm[i][k],j-1);             if(f[i][k]