BZOJ 1133 [POI2009]Kon DP

题意:链接略方法: DP解析:首先DP式子很容易写出来。设f[i][j]表示前i站查了j次票，并且第i站后要查的最大人数。f[i][j]=max(f[k][j-1]+peo[x][y])(k<i&&k<=x<i,y>=i)这样如果我们枚举x,y的话很可能达到O(n^4)左右的复杂度。所以考虑优化这个部分。设sum[i][j]=\sum{peo[x][y]}&&x<=i,i<y<=j于是注意sum的更新。代码:using namespace std;int n,k;int sum[N][N];int peo[N][N];int pre[N][K];int f[N][K]; int main(){scanf(“%d%d”,&n,&k);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)scanf(“%d”,&peo[i][j]);for(int i=1;i<=n;i++){sum[i][n]=sum[i-1][n]+peo[i][n];for(int j=n-1;j>=1;j–){sum[i][j]=sum[i-1][j]+sum[i][j+1]-sum[i-1][j+1]+peo[i][j];}}memset(f,-1,sizeof(f));f[0][0]=0;for(int l=1;l<=k;l++){for(int i=l;i<n;i++){for(int j=l-1;j<=i-1;j++){if(f[j][l-1]!=-1){if(f[j][l-1]+sum[i][i+1]-sum[j][i+1]>f[i][l]){f[i][l]=f[j][l-1]+sum[i][i+1]-sum[j][i+1];pre[i][l]=j;}}}}}int ma=0,no;for(int i=k;i<n;i++)if(f[i][k]>ma)ma=f[i][k],no=i;int ans[N];int cnt=0;while(k){ans[++cnt]=no;no=pre[no][k];k–;}for(int i=cnt;i>=2;i–)printf(“%d “,ans[i]);printf(“%d\n”,ans[1]);}

，不要害怕错过什么，因为在路上你就已经收获了自由自在的好心情。