Solution - 打砖块

这题一看就是一道 \(dp\)

我们可以定义两个辅助数组 \(dn[i][j]\) 和 \(dy[i][j]\)

\(dn[i][j]\) 表示在第 \(i\) 列打 \(j\) 枪最后一枪打在 \(\rm N\) 上所得分数

\(dy[i][j]\) 表示在第 \(i\) 列打 \(j\) 枪最后一枪打在 \(\rm Y\) 上所得分数

然后我们就可以开始 \(dp\) 了

---

定义 \(:\)

\(dpn[i][j]\) 表示在前 \(i\) 列打 \(j\) 枪最后一枪打在 \(\rm N\) 上所得最大分数

\(dpy[i][j]\) 表示在前 \(i\) 列打 \(j\) 枪最后一枪打在 \(\rm Y\) 上所得最大分数

---

三层循环 \(i,j,l\) 分别枚举前 \(i\) 列，打 \(j\) 发子弹，在第 \(i\) 列打 \(l\) 发子弹

状态转移：

\[dpy_{i,j} = \max(dpy_{i,j}, dpy_{i-1,j-1} + dy_{i,l}) \]

\[dpn_{i,j} = \begin{cases} \max(dpn_{i,j},\ dpy_{i-1,j-l}+dn_{i,l}), & \text{if }l \ne 0 \\ \max(dpn_{i,j},\ dpn_{i-1,j-l}+dy_{i,l}), & \text{if }j \ne 0 \end{cases} \]

---

此算法时间复杂度为 \(\mathcal{O}(nmk)\)

最后给出 \(code\)

#include 
using namespace std;
int n, m, k;
bool c[205][205];
char x;
int a[205][205];
int dy[205][405], dn[205][405], dpn[205][405], dpy[205][405];
int main() {
	scanf("%d %d %d\n", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j] >> x;
			if (x == 'Y') c[i][j] = 1;
		}
	}
	for (int j = 1; j <= m; j++) {
		int tot = 0;
		for (int i = n; i >= 1; i--) {
			if (c[i][j] == 1) dy[j][tot] += a[i][j];
			else {
				tot++;
				dn[j][tot] = dy[j][tot - 1] + a[i][j];
				dy[j][tot] = dn[j][tot];
			} 
		}
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= k; j++) {
			for (int l = 0; l <= min(j, n); l++) {
				dpy[i][j] = max(dpy[i][j], dpy[i - 1][j - l] + dy[i][l]);
				if (l != 0) dpn[i][j] = max(dpn[i][j], dpy[i - 1][j - l] + dn[i][l]);
				if (j != l) dpn[i][j] = max(dpn[i][j], dpn[i - 1][j - l] + dy[i][l]);
			}
		}
	}
	printf("%d", dpn[m][k]);
	return 0;
}