## Meaning:

N layers of bricks are placed in a groove, n bricks are placed in the uppermost layer, and one brick is reduced in each layer from top to bottom. Each brick has a score. Knock off the brick to get the corresponding score, as shown in the figure below:

14 15 4 3 23 33 33 76 2 2 13 11 22 23 31

If you want to knock off the j-th brick of the i-th layer, if i=1, you can knock it off directly; If I > 1, you must knock off the J and j+1 bricks of layer i-1 first.

You can now knock down up to m bricks and ask for the maximum score.

## Solution:

Obviously, it is dynamic programming. At the beginning, the state set as dp[i][j][k] indicates that the k-th brick is knocked to the maximum value of (i,j). However, there is no way to do this, because dynamic programming has no aftereffect, and we need to consider the previous choices

It's embarrassing now. There are aftereffects from top to bottom or from bottom to top. Then we can push from left to right or from right to left

We began to consider pushing from right to left. If I want to hit bricks (x,y), I must hit the bricks directly above and in the upper right corner. The bricks directly above should be considered for knocking off (x,y), while the bricks in the upper right corner can be considered for knocking off the bricks on the right

what do you mean? Look at the picture

Now we want to make blue bricks (2,1). The two orange parts must have been knocked out. The bricks in the same column as the blue bricks are knocked out this time, and the bricks (1,2) in the upper right corner can be made through state transfer, because we deal with them from right to left, and the right has been dealt with. Then (3,2) the purple bricks have been dealt with, If the purple bricks are to be hit, the (1,2) bricks on the upper side must also be hit, so we can transfer from the state of column i+1 to the state of column i

That is, when processing (i,j), the bricks in this column need to be processed now, and the bricks in the upper right corner can be obtained from the state of the previous column (j+1 column)

This treatment has no aftereffect

This results in:

d
p
[
i
]
[
j
]
=
m
a
x
i
−
1
<
=
p
<
=
n
−
i
(
d
p
[
p
]
[
j
+
1
]
)
+
∑
p
=
1
i
a
[
p
]
[
j
]
dp[i][j]=max_{i-1<=p<=n-i}(dp[p][j+1])+\sum_{p=1}^ia[p][j]
dp[i][j]=maxi−1<=p<=n−i(dp[p][j+1])+p=1∑ia[p][j]

Let's take the number of knock bricks into account

Let dp[i][j][k]: indicates that K bricks have been knocked, and the K knock is the maximum score of (i,j)

d
p
[
i
]
[
j
]
[
k
]
=
m
a
x
i
−
1
<
=
p
<
=
n
−
i
(
d
p
[
p
]
[
j
+
1
]
[
k
−
i
]
)
+
∑
p
=
1
i
a
[
p
]
[
j
]
dp[i][j][k]=max_{i-1<=p<=n-i}(dp[p][j+1][k-i])+\sum_{p=1}^ia[p][j]
dp[i][j][k]=maxi−1<=p<=n−i(dp[p][j+1][k−i])+p=1∑ia[p][j]

## code:

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) { x= 0; char c= getchar(); bool flag= 0; while (c < '0' || c > '9') flag|= (c == '-'), c= getchar(); while (c >= '0' && c <= '9') x= (x << 3) + (x << 1) + (c ^ 48), c= getchar(); if (flag) x= -x; read(Ar...); } template <typename T> inline void write(T x) { if (x < 0) { x= ~(x - 1); putchar('-'); } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #else startTime = clock (); freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #else endTime= clock(); printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=55; int dp[maxn][maxn][3020]; int a[maxn][maxn]; int sum[maxn][maxn]; int main() { //rd_test(); int n,m; read(n,m); for(int i=1;i<=n;i++){ for(int j=1;j<=n-i+1;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n-i+1;j++){ sum[j][i]=sum[j-1][i]+a[j][i]; } } memset(dp,-127,sizeof(dp)); dp[0][n+1][0]=0; int ans=0; for(int j=n;j>=1;j--){//column for(int i=0;i<=n-j+1;i++){//that 's ok for(int k=i;k<=m;k++){ for(int p=max(0,i-1);p<=n-j;p++){ if(dp[p][j+1][k-i]!=-1){ dp[i][j][k]=max(dp[i][j][k],dp[p][j+1][k-i]+sum[i][j]); ans=max(ans,dp[i][j][k]); } } } } } cout<<ans; //Time_test(); }