[洛谷P1174]打砖块

题目

传送门 to luogu

题目大意：$***$∗∗∗（已和谐）

思路

把砖块叫做$N$N类与$Y$Y类（意义见题面）。
把最优解中依次打碎的 砖块的类别 写成一个序列，应该长这样：$?,?,?,\dots,N$?,?,?,…,N（最后一个一定是$N$N类砖块，如果是$Y$Y类砖块，那么你就会剩一颗子弹 除非你进入了下一关）。
首先，肯定有$k=|\mathbb N|$k=∣N∣（即$N$N类砖的数量等于$k$k）。
发现在打最后一个砖块之前（也就是刚刚打完倒数第二个砖块的时候），剩下一颗子弹。而 子弹的数量是单调不增的（随着时间的推移 游戏难度逐渐增大），所以前面的可以随便重新排列，子弹不会耗尽。把同一列的砖块搞到一起，相当于砖块是 一列一列的打碎 的！
这为 分组背包 奠定了思想基础 （我才不是历史老师呢）。
说起来，列与列之间的顺序好像也可以随便乱搞？只要 留一个$N$N类砖块在最后 就是合法方案！
当然，整局游戏中最后一个打碎的砖块肯定是某一列中打碎了的、最上面的砖块。
所以可以愉快地$dp$dp啦！
$with_x(y)$withx​(y)表示前$x$x列中有$y$y个$N$N类砖且 至少有一列满足要打碎的最上面一块是$N$N类别，$without_x(y)$withoutx​(y)为无限制条件。明显$\mathrm{without}_x(y)\ge \mathrm{with}_x(y)$withoutx​(y)≥withx​(y)。
转移就很简单了：
$\begin{cases} \operatorname{Note}\thickspace c=|\mathbb{N}|,v=\sum f\\ \mathrm{without}_{x}(y)=\mathrm{without}_{x-1}(y-c)+v\\ \mathrm{with}_{x}(y)=\mathrm{without}_{x-1}(y-c)+v & (\mathrm{this\space column}=N)\\ \mathrm{with}_{x}(y)=\mathrm{with}_{x-1}(y-c)+v \end{cases}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​Notec=∣N∣,v=∑fwithoutx​(y)=withoutx−1​(y−c)+vwithx​(y)=withoutx−1​(y−c)+vwithx​(y)=withx−1​(y−c)+v​(this column=N)​

其实就是对这一列要打碎的砖块进行枚举，然后转移。
最后输出$\mathrm{with}_n(k)$withn​(k)就好啦！

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int MaxN = 200; const long long infty = (1ll<<62)-1;
int cost[MaxN][MaxN], val[MaxN][MaxN], n, m, k;
// 可以滚动一下，其实不滚动也不会爆，但是感觉很NB 
long long with[2][MaxN+1], without[2][MaxN+1]; // 千万不要写成[2][200]! 

int main(){
	scanf("%d %d %d",&n,&m,&k);
	bool excess = true; // 可以通关 
	for(int i=0, allCost = 0; i<n; ++i){
		char c;
		for(int j=0; j<m; ++j){
			scanf("%d %c",&val[i][j],&c);
			cost[i][j] = (c=='N'?1:0);
			allCost += cost[i][j];
		}
		if(allCost >= k)
			excess = false;
	}
	for(int Shoot=0; Shoot<=k; ++Shoot){
		with[1][Shoot] = -infty; // impossible 
		without[1][Shoot] = 0;
	}
	for(int j=0; j<m; ++j){
		int Cost, Val; Cost = Val = 0;
		for(int Shoot=0; Shoot<=k; ++Shoot){
			with[j&1][Shoot] = with[(j&1)^1][Shoot];
			without[j&1][Shoot] = without[(j&1)^1][Shoot];
		} // 饶这一列不死 
		for(int i=n-1; ~i; --i){
			Val += val[i][j]; Cost += cost[i][j];
			for(int Shoot=Cost; Shoot<=k; ++Shoot){
				if(cost[i][j] == 1) // 这一列要打碎的砖块最后一个是N类 
					with[j&1][Shoot] = max(with[j&1][Shoot],without[(j&1)^1][Shoot-Cost]+Val);
				with[j&1][Shoot] = max(with[j&1][Shoot],with[(j&1)^1][Shoot-Cost]+Val);
				without[j&1][Shoot] = max(without[j&1][Shoot],without[(j&1)^1][Shoot-Cost]+Val);
			}
		}
	}
	printf("%lld",excess?without[(m&1)^1][k]:with[(m&1)^1][k]);
	return 0;
}
// 数组不要开小了…… 
// 蒟蒻在此用个人经验告诉你：k=200的数据有5组！ 

附一张惨痛的越界教训：