[LUOGU1437] 敲砖块

题目描述

在一个凹槽中放置了 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次，我们会发现这个设法使有后效性的。

我们在dp的时候是会对后面产生影响的，而我们不可能记录状态（别说要状压）；

所以我们要从后往前考虑，设f[i][j][k]表示已经打了后i列，正在第j行，一共打了k次的最大价值；

f[i][j][k] = max(f[i+1][t][k-j] + a[1][i]+...+a[j][i])，后面的那一堆我们可以用前缀和优化；

t的循环从j-1 ~ n-i;因为我们打到地下了，必须要把它之上的全部打通，所以j-1是下限,n-i是上限，

为什么是n-i而不是n-i+1？因为 ... n - (i + 1) + 1...

这也解释了后面的那么多的和是为什么。

然后这道题就抄会了...

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

inline int read()

{

    int res=;char ch=getchar();bool fl=;

    while(!isdigit(ch)){if(ch=='-')fl=;ch=getchar();}

    while(isdigit(ch)){res=(res<<)+(res<<)+(ch^);ch=getchar();}

    return fl?-res:res;

}

int n, m, f[][][]; //从后往前第i列，第j个，打了k次

int a[][];

int main()

{

    n = read(); m = read();

    for (register int i =  ; i <= n ; i ++)

        for (register int j =  ; j <= (n - i + ) ; j ++)

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

    int sum = ;

    memset(f, -, sizeof f);

    f[n+][][] = ;

    for (register int i = n ; i >=  ; i --)

    {

        int sum = ;

        for (register int j =  ; j <= n - i +  ; j ++)

        {

            sum += a[j][i];

            for (register int k = j ; k <= m ; k ++)

            {

                for (register int t = max(, j - ) ; t <= n - i ; t ++)

                {

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

                }

            }

        }

    }

    int ans=;

    for (register int i =  ; i <= n ; i ++)

    {

        for (register int j =  ; j <= n - i +  ; j ++)

        {

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

        }

    }

    cout << ans;

    return ;

}

巴特西

[LUOGU1437] 敲砖块

题目描述

输入输出格式

输入输出样例

最新文章

热门文章