洛谷 P1437 [HNOI2004]敲砖块 题解【DP】【前缀和】

点击量：157

DPDPDP+细节……

目录

题目描述

在一个凹槽中放置了n层砖块、最上面的一层有n块砖，从上到下每层依次减少一块砖。每块砖都有一个分值，敲掉这块砖就能得到相应的分值，如下图所示。

14 15 4 3 23
 33 33 76 2
   2 13 11
    22 23
     31

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

 

你现在可以敲掉最多m块砖，求得分最多能有多少。

输入输出格式

输入格式：

输入文件的第一行为两个正整数n和m；接下来n行，描述这n层砖块上的分值a[i][j],满足0≤a[i][j]≤100。

 

对于 100%的数据，满足1≤n≤50，1≤m≤n*(n+1)/2；

 

输出格式：

输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。

 

输入输出样例

输入样例#1：

4 5

2 2 3 4

8 2 7

2 3

49

输出样例#1：

19

14 15 4  3 23
33 33 76 2
2  13 11
22 23
31

   这样我们就发现：如果砖块(i,j)（第i行第j列）能够被打掉，那么它右边那一列的最上面j-1块砖块一定被打掉了。状态就可以从右边那一列自j-1行到最后一行转移过来，而且这样的状态基本是全面的，dp数组为f[i][j][k]，表示打掉第i行第j列后，已经打掉了k块时的最大收益，其中k<=m时可更新最大结果。不过还会有一种状态，就是多段被打掉的区块不连通，像这样：

   如果红色区块是最优解，那么像我们这样计算，最暴力的做法是枚举每个点对，看它们分别能造成多大的收益，不过这样状态不全面，有错误，而且时间复杂度是会达到$ m^3(m=\frac{n(n+1)}{2})$的，不可取。

   既然我们的状态是从j-1开始转移的，那么1就是从0开始转移——其实只要在不考虑这种状况的情况下扩大j的枚举下界到0即可。我们用0存过渡状态，f[i][0][k]就表示在第i列（不含）右边，合法地（已转移的状态保证合法）打掉k个砖块后的最大收益。f[i][0][k]可以由f[i+1][0..n-i][k]中任何一个状态转移过来，这是一个比较重要的细节，也是很多人（包括我）65分的原因。

   这样状态转移方程就是：f[i][j][k]=max{f[i+1][j-1…n-i][k-j]}(n-i表示i+1列的数的个数)，并注意越界。

   总的来说，这个题还是比较难想的，我们只要把这种模型题“信息学化”，把它放到二维数组中，思维就可以扩展到很广了。

Code：

#include<cstdio>
#include<cstring>
int max(int x,int y)
{
    return x>y?x:y;
}
int f[55][55][1300];
int b[55][55];

int main()
{
    memset(b,0,sizeof(b));
    memset(f,0,sizeof(f));
    int n,m,u;
    int ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n-i+1;j++)
        {
            scanf("%d",&u);
            b[i][j]=b[i-1][j]+u;
        }
    //从右往左自上而下DP
    for(int i=n;i>=1;i--)
        for(int j=0;j<=n-i+1;j++)
        //对于j,i点
            //从它右边的k,i+1转移过来，其中k>=j-1
            for(int k=max(0,j-1);k<=n-i;k++)
                for(int t=(k+1)*k/2;t+j<=m;t++)
                {
                    f[j][i][t+j]=max(f[j][i][t+j],f[k][i+1][t]+b[j][i]);
                    if(f[j][i][t+j]>ans)
                        ans=f[j][i][t+j];
                }

    printf("%d\n",ans);
    return 0;
}