2018.08.16 洛谷P1437 [HNOI2004]敲砖块（二维dp）

传送门
看起来普通$dp$像是有后效性的样子。。。
继续分析：如果我们第i+1列的最优值已经处理出来了，那么第i列的最优值就跟第i+1列没有关系了。
因为只要保证第i+1列至少挖到了第i-1行就行，如何保证？从第i+1列的第i-1行开始对第i列转移就行了，注意边界其实这题不难。
主要是要想到要从前一列的状态来推出当前列的状态。
事实上，如果我们用f[i][j][k]表示正在挖第i行j列的砖块，已经挖了k个，那么$f[t][j+1][k-i](i-1\le t \le n-j)$是可以对$f[i][j][k]$做出贡献的，不难想到从前者转移过来需要将第i列的第1~i行的砖块都挖掉，因此转移的时候记录一个前缀和用于转移就行了。
代码：

#include
#define inf 0x3f3f3f3f 
using namespace std;
int n,K,a[55][55],f[55][55][3005],ans=0;
int main(){memset(f,-inf,sizeof(f)),scanf("%d%d",&n,&K),f[0][n+1][0]=0;for(int i=1;i<=n;++i)for(int j=1;j<=n-i+1;++j)scanf("%d",&a[i][j]);for(int j=n;j;--j)for(int i=0,sum=0;i<=n-j+1;sum+=a[++i][j])for(int k=i;k<=K;++k)for(int t=max(0,i-1);t<=n-j;++t)f[i][j][k]=max(f[i][j][k],f[t][j+1][k-i]+sum);for(int i=1;i<=n;++i)for(int j=1;j<=n-i+1;++j)ans=max(ans,f[i][j][K]);cout<return 0;
}

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