题解 P1437 【[HNOI2004]敲砖块】

YoungLove · 2017-10-30 17:21:23 · 题解

Youngsc

并没有去旋转三角形。

首先定义f[i][j][k]表示从后往前打到第i列第j个且一共打了k次的最大分数。

由于题目中已知，如果我想打一个砖块，那么我必须将他正上方和右上方的砖块都打，所以打到第i列第j就意味着这一列打掉的砖块为1,2,\ldots,j,对于此我们用前缀和去维护\sum_{1}^j a[i][j]。

为了避免后效性，我们从后往前枚举列那么状态转移方程就是f[j][i][k] = Max(f[j+1][t][k-i]+\sum_{1}^j{a[i][j]})，当然t只能从i-1到n-j。

安利博客 (Youngsc)[http://youngsc.ml/]

代码在这里

# include <bits/stdc++.h>
# define R register
# define LL long long
using namespace std;

int n,m,a[55][55],ans,f[55][55][3010];

template <typename T> inline void in(R T& a){
    R char c=getchar();R int x=0,f=1;
    while (!isdigit(c)){if(c == '-') f=-1; c=getchar();}
    while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c = getchar();
    a=x*f;
}

template <typename T> inline void maxx(R T& a,const T b){a<b? a=b:0;}
template <typename T> inline void minn(R T& a,const T b){a>b? a=b:0;}

int main(){
    // freopen("makechess.in","r",stdin);
    // freopen("makechess.out","w",stdout);
    in(n),in(m);
    memset(f,-127,sizeof(f));//避免不合法状态转移
    f[n+1][0][0] = 0;//初始化合法状态
    for(R int i=1; i<=n; ++i)
        for(R int j=1; j<=n-i+1; ++j)
            in(a[i][j]);

    for(R int j=n; j>=1; --j)
        for(R int i=0,sum=0; i<=n-j+1; ++i,sum+=a[i][j])
            for(R int k=i; k<=m; ++k)
                for(R int l=max(0,i-1); l<=n-j; ++l)
                    maxx(f[j][i][k],f[j+1][l][k-i]+sum);
    for(R int i=1; i<=n; ++i)
        for(R int j=1; j<=n-i+1; ++j)
            maxx(ans,f[i][j][m]);
    printf("%d",ans);
}