洛谷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：复制

输出样例#1：复制

非常妙的一道题目

首先我们最先想到的肯定是$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 + , INF = 1e9 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M, f[][][], a[][];

main() {

#ifdef WIN32

    //freopen("a.in", "r", stdin);

#endif

    N = read(); M = read();

    for(int i = ; i <= N; i++)

        for(int j = ; j <= N - i + ; j++)

            a[i][j] = read();

    memset(f, -0x3f, sizeof(f));

    f[N + ][][] = ;

    for(int j = N; j >= ; j--) {

        int sum = ;

        for(int i = ; i <= N - j + ; i++, sum += a[i][j])

            for(int k = i; k <= M; k++) {

                for(int l = max(, i - ); l <= N - j; l++)

                    f[j][i][k] = max(f[j][i][k], f[j + ][l][k - i] + sum);

            }

    }

    int ans = ;

    for(int i = ; i <= N; i++)

        for(int j = ; j <= N - i + ; j++)

            ans = max(ans, f[i][j][M]);

    printf("%d", ans);

    return ;

}

巴特西

洛谷P1437 [HNOI2004]敲砖块(dp)

题目背景

题目描述

输入输出格式

输入输出样例

最新文章

热门文章