洛谷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；

輸出格式：

輸出文件僅一行為一個正整數，表示被敲掉磚塊的最大價值總和。

輸入輸出樣例

4 5
2 2 3 4
8 2 7
2 3
49

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;
}