[hnoi2004]敲砖块 (洛谷1437)

Posted by yjjr's blog on February 6, 2018

标签:DP

题目描述

在一个凹槽中放置了 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

 

设f[i][j][k]表示前i行打到第j列,共打了k次所能得到的最大分数

注意要从右向左处理,不然很容易WA

 

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
const int maxn=60;
int s[maxn][maxn],f[maxn][maxn][maxn*(maxn+1)/2],a[maxn][maxn];
int n,m,ans=0,x;

int main()
{
    mem(s,0);mem(f,-1);
    scanf("%d%d",&n,&m);
    f[n+1][0][0]=0;
    rep(i,1,n)
        rep(j,1,n-i+1)scanf("%d",&a[i][j]);
    rep(j,1,n)
        rep(i,1,n-j+1)s[i][j]=s[i][j-1]+a[j][i];
    dep(i,n,1)
        rep(j,0,n-i+1)
            rep(k,j,m)
                rep(r,j?j-1:0,n-i)
                if(f[i+1][r][k-j]!=-1)
                    f[i][j][k]=max(f[i][j][k],f[i+1][r][k-j]+s[i][j]);
    rep(i,1,n)
        rep(j,0,n-i+1)
            ans=max(ans,f[i][j][m]);
 /*   rep(i,1,n){
        rep(j,0,i)
           printf("%d ",f[i][j][m]);
       printf("\n");
   }*/
    printf("%d\n",ans);
    return 0;
}




本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr