OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HNOI2004】打砖块

【题目描述】

在一个凹槽中放置了n层砖块,最上面的一层有n块砖,第二层有n-1块,……最下面一层仅有一块砖。第i层的砖块从左至右编号为1,2,……i,第i层的第j块砖有一个价值a(a<=50)。下面是一个有5层砖块的例子:



如果你要敲掉第i层的第j块砖的话,若i=1,你可以直接敲掉它,若i>1,则你必须先敲掉第i-1层的第j和第j+1块砖。

你的任务是从一个有n(n<=50)层的砖块堆中,敲掉(m<=500)块砖,使得被敲掉的这些砖块的价值总和最大。

【输入】

第一行为两个正整数,分别表示n,m,接下来的第i每行有n-i+1个数据。

【输出】

仅有一个正整数,表示被敲掉砖块的最大价值总和。

【输入样例】

4 5

2 2 3 4

8 2 7

2 3

49

【输出样例】

19

【题解】

理清题意,发现同一行可以被打掉的砖块是可以无规律分布的,但每一列只能打掉从上往下连续的砖块,所以考虑按照每一列DP。

设计状态f[i][j][k]表示打到第i列时、当前这一列打掉从上往下连续j块砖、包括这一列打掉的这一列在内共计打掉了k块砖时,最大的价值总和。对于打掉砖的条件,是这块砖上面所有的砖都被打掉、以及前一列在这块砖上面的砖也都被打掉,前者在状态中已经表示了,后者可以在转移时加以限制。

对于计算每一列前j块砖的价值总和,前缀和处理后就可以O(1)得到了。

状态转移方程:f[i][j][k]=Max(f[i-1][p][k-j]+sum[i][j]),j-1≤p≤i-1,其中sum[i][j]表示第i列打掉前j块砖的最大分数。

【代码】

时间复杂度O(n^3*m),但常数非常小~

http://paste.ubuntu.com/8086891/

评论

© OI技术宅 | Powered by LOFTER