专栏首页数据结构与算法洛谷P1437 [HNOI2004]敲砖块(dp)

洛谷P1437 [HNOI2004]敲砖块(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$个的最大价值

但是这样由于第一行的缘故是有后效性的

转换一下思路,用$f[i][j][k]$表示第$i$列,第$i$个,选了$k$

转移的时候倒着枚举列,这样就不会有后效性了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
//#define int long long 
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, f[51][51][5001], a[5001][5001]; 
main() { 
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    N = read(); M = read();
    for(int i = 1; i <= N; i++) 
        for(int j = 1; j <= N - i + 1; j++)
            a[i][j] = read();
    memset(f, -0x3f, sizeof(f));
    f[N + 1][0][0] = 0;
    for(int j = N; j >= 1; j--) {
        int sum = 0;
        for(int i = 0; i <= N - j + 1; i++, sum += a[i][j]) 
            for(int k = i; k <= M; k++) {
                for(int l = max(0, i - 1); l <= N - j; l++)
                    f[j][i][k] = max(f[j][i][k], f[j + 1][l][k - i] + sum);
            }
    }
    int ans = 0;
    for(int i = 1; i <= N; i++) 
        for(int j = 1; j <= N - i + 1; j++)
            ans = max(ans, f[i][j][M]);
    printf("%d", ans);
    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 05:Cave Cows 1 洞穴里的牛之一

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 很少人知道其实奶牛非常喜欢到洞穴里面去探险。     洞窟里有N...

    attack
  • BZOJ5249: [2018多省省队联测]IIIDX(线段树 贪心)

    不难发现题目给出的是一个树,其中\(\frac{i}{K}\)是\(i\)的父亲节点

    attack
  • 10:Challenge 3(树状数组直接修改)

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

    attack
  • 1061 判断题 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • CodeForces 1143A The Doors

    ShenduCC
  • 05:Cave Cows 1 洞穴里的牛之一

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 很少人知道其实奶牛非常喜欢到洞穴里面去探险。     洞窟里有N...

    attack
  • 搜索专题

    POJ  Best Sequence http://poj.org/problem?id=1699 题意:给你n个字符窜,求其所能拼接的最短长度。 分析:预处理...

    用户1624346
  • 1072 开学寄语 (20 分)

    可爱见见
  • Java实现图片的滤镜效果滤镜实现总结

    在移动端或者在web开发时处理图片都是一件麻烦的事儿。我调研过很多library,特别是在移动端处理图片时动不动都需要使用 C++ 或者 OpenCV。这对于 ...

    fengzhizi715
  • 2015-偶数求和

    有一个长度为n(n<=100)的数列,该数列定义为从2开始的递增有序偶数,现在要求你按照顺序每m个数求出一个平均值,如果最后不足m个,则以实际数量求平均值。编程...

    用户2038589

扫码关注云+社区

领取腾讯云代金券