Sol-Dp-敲砖块

设F[i][j][k]表示打到第i行第j个打了k次的权值

转移显然: F [ i ] [ j ] [ k ] = m a x { F [ i + 1 ] [ t ] [ k − j ] + ∑ y [ j ] [ q ] } F[i][j][k] = max\{F[i+1][t][k−j]+∑y[j][q]\} F[i][j][k]=max{F[i+1][t][k−j]+∑y[j][q]}

前缀和优化转移 ,复杂度 O ( N 2 M ) O(N^2M) O(N2M)

# include 
# define R register
# define LL long long
using namespace std;int f[55][55][3010] ;
int a[55][55] ;
int n,m,ans ; 
#define loop(I,X,Y) for(R int I = (X) ; I <= (Y) ; ++I)
#define lp(I,X,Y) for(R int I = (X) ; I >= (Y) ; --I)#define in(X) scanf("%d",&X)int main(){scanf("%d%d",&n,&m) ;memset(f,-127,sizeof(f)) ;f[n+1][0][0] = 0 ;loop(i,1,n)for(R int j=1; j<=n-i+1; ++j)in(a[i][j]);lp(j,n,1)for(R int i=0,sum=0; i<=n-j+1; ++i,sum+=a[i][j])loop(k,i,m)for(R 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);loop(i,1,n)for(R int j=1; j<=n-i+1; ++j)ans = max(ans,f[i][j][m]);printf("%d",ans);
}