【[HNOI2004]敲砖块】

非常巧妙的\(dp\)顺序

这道题如果按照最正常的顺序来\(dp\)的话，显然是没有办法做的，后效性太大了

所以我们可以巧妙的改变\(dp\)的顺序

我们注意到一个位置\((i,j)\)要被打到的话就必须将其右上方的所有砖块都打掉，于是我们我们设\(dp[i][j][k]\)表示打到了\((i,j)\)这个位置一共打了\(k\)个，其中\((i,j)\)被打掉了的最大值

如果我们改变一下\(dp\)顺序，从右向左对每列从上到下做\(DP\),我们就可以转移了

方程

\[dp[i][j][k]=max(dp[p][j+1][k-i]+\sum_{t=1}^{j}a[i][t])
\]

我们枚举左边那一列，如果打掉左边那一列上的\((p,j+1)\)的位置，那么就相当于\((i,j)\)左边被清空了，于是我们在打掉\((i,j)\)往上的一列就好了

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define maxn 51

inline int read()

{

    char c=getchar();

    int x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9')

        x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

int dp[maxn][maxn][1505];

int a[maxn][maxn];

int n,m,ans,tot,sum;

int main()

{

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

    for(re int i=1;i<=n;i++)

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

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

    memset(dp,-20,sizeof(dp));

    tot=1;

    dp[0][n+1][0]=0;

    for(re int i=1;i<=n;i++) dp[0][i][0]=0;

    for(re int j=n;j>=1;--j,sum=0)

        for(re int i=0;i<=n-j+1;i++)

        {

            tot++;

            sum+=a[i][j];

            for(re int k=i;k<=m;k++)

            {

                if(k>tot) break;

                for(re int p=max(0,i-1);p<=n-j;p++)

                    dp[i][j][k]=max(dp[i][j][k],dp[p][j+1][k-i]+sum);

                ans=max(dp[i][j][k],ans);

            }

        }

    std::cout<<ans;

    return 0;

}

巴特西

【[HNOI2004]敲砖块】

最新文章

热门文章