题解：HNOI2004 敲砖块 【DP】

作为一个小蒟蒻，感觉自己的DP已经菜的要死了…
省选前抱普及的佛脚

这个题目大佬们说要旋转，然后本蒟蒻不会…
怎么看都像是树形背包
但是他上面的两个转移过来中间有重叠，所以和树形背包没有任何关系…压根就不是一棵树…

于是开始磕…

int main()
{n=read(),m=read();for(int i=1;i<=n;++i){for(int j=1;j<=(n-i+1);++j)a[i][j]=read();}for(int i=1;i<=n;++i){for(int j=1;j<=(n-i+1);++j)s[j][i]=s[j-1][i]+a[j][i];}memset(f,-1,sizeof(f));for(int i=1;i<=n+1;++i)f[0][i][0]=0;f[1][n][1]=a[1][n];for(int i=n;i>0;--i){for(int j=(n-i+1);j>=0;--j)for(int k=0;k<=m;++k)if(f[j][i][k]!=-1){for(int l=min(j+1,m-k);l>=0;l--){f[l][i-1][k+l]=max(f[l][i-1][k+l],f[j][i][k]+s[l][i-1]);}}}int maxn=-1;for(int i=1;i<=n;++i){for(int j=0;j<=(n-i+1);++j)maxn=max(f[i][j][m],maxn);}cout<<maxn;return 0;
}

我太弱了

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！