【洛谷 P1437】 [HNOI2004]敲砖块（DP）

毒瘤DP题

因为\((i,j)\)能不能敲取决于\((i-1,j)\)和\((i-1,j+1)\)，所以一行一行地转移显然是有后效性的。

于是考虑从列入手。我们把这个三角形“左对齐”，变成一个直角三角形。

第\(i\)列第\(j\)个要取，则第\(i\)列前\(j-1\)个和第\(i+1\)列前\(j-1\)个肯定是都要取的。

于是设\(f[i][j][k]\)表示第\(i\)列第\(j\)个要取，且总共已经去了\(k\)个的最大得分，

我们枚举第\(i+1\)列取多少个，则有

\[f[i][j][k] = max(f[i][j][k], f[i + 1][p][k - j] + sum[i][j])
\]

其中\(p\in [j-1,n-i]\)，\(sum[i][j]\)是预处理出来的第\(i\)列前\(j\)个的前缀和。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

#define Close fclose(stdin);fclose(stdout);

const int MAXN = 55;

const int MAXM = 1300;

int a[MAXN][MAXN], sum[MAXN][MAXN], f[MAXN][MAXN][MAXM];

int n, m, ans;

int main(){

	Open("brike");

	scanf("%d%d", &n, &m);

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

		for(int j = n; j >= i; --j)

			scanf("%d", &a[i][n - j + 1]);

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

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

	      sum[i][j] = a[j][i] + sum[i][j - 1];

    memset(f, -1, sizeof f);

    for(int i = 1; i <= n; ++i) f[i][1][1] = a[1][i];

	for(int i = n; i; --i)

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

	      for(int k = j; k <= m; ++k)

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

	            if(p >= 0)

                  if(~f[i + 1][p][k - j])

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

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

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

          ans = max(ans, f[i][j][m]);

	printf("%d\n", ans);

	return 0;

}

巴特西

【洛谷 P1437】 [HNOI2004]敲砖块（DP）

最新文章

热门文章

巴特西

【洛谷 P1437】 [HNOI2004]敲砖块 （DP）

最新文章

热门文章

【洛谷 P1437】 [HNOI2004]敲砖块（DP）