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

作者: wjyyy 分类: DP,解题报告 发布时间: 2018-06-19 17:35

点击量:23

 

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
   这个题类似杨辉三角的结构,难道是递推?不过打掉的砖块不一定构成三角形,所以是多种情况叠加,就联想到DP了。
   首先以为是容斥原理,就是如果上面相邻两个状态转移下来,是要减去上面多算的,不过这种做法实在是枚举不完,索性考试时放掉了,这种做法极限枚举有5分。
   如果直接DP的话,是非常难构思的,而且有后效性,因此我们根据输入时的数据以及数组的性质,将其左对齐,那么样例就变成了:
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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */