[HNOI2004] 敲砖块
2024年12月24日小于 1 分钟
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[55][55];
int cnt[55][55]; //列向下计数
int sum[55][55]; //列向下求和
int dp[55][55][50 * 51 / 2 + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= i; j++)
{
cin >> a[i][j];
cnt[i][j] = cnt[i + 1][j] + 1;
sum[i][j] = sum[i + 1][j] + a[i][j];
}
}
n++;
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; i++)
dp[n][i][0] = 0;
for (int j = 1; j <= n; j++)
{
for (int i = n; i >= 1; i--)
{
if (j > i)
break;
for (int k = 1; k <= m; k++)
{
if (dp[i - 1][j - 1][k - cnt[i][j]] != -1)
dp[i][j][k] = dp[i - 1][j - 1][k - cnt[i][j]] + sum[i][j];
if (dp[i][j - 1][k - cnt[i][j]] != -1)
{
if (dp[i][j][k] == -1)
dp[i][j][k] = dp[i][j - 1][k - cnt[i][j]] + sum[i][j];
else
dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - cnt[i][j]] + sum[i][j]);
}
if (dp[i + 1][j][k - 1] != -1)
{
if (dp[i][j][k] == -1)
dp[i][j][k] = dp[i + 1][j][k - 1] + a[i][j];
else
dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k - 1] + a[i][j]);
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, dp[n][i][m]);
cout << ans << "\n";
return 0;
}