题目描述
为了庆祝自己的生日，小张推出一款游戏。游戏在一个20×20的方格上进行，上面有一些怪物，用“#”表示，其他是空格，用“.”表示。怪物有两点体力。体力为0时死亡。
你可以进行以下操作：
（1）使一个横行上的怪物体力减一
（2）使一个竖行上的怪物体力减一
对每个横行或竖行只能操作一次，限定n次，问最多能杀死多少个怪物。
输入格式
第一行为整数n（1≤n≤40），表示操作的次数。
接下来是一个20×20的方格，“#”表示怪物，“.”表示空格。
输出格式
一行，输出最多能杀死的怪物数量。
输入样例一
3
....................
....................
..###...............
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
输出样例一
2
输入样例二
10 #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### ####################
输出样例二
25
题解
容易想到，如果想杀$(i,j)$的怪物，必须对第$i$行和第$j$列做操作。
那么我们可以对行操作进行搜索，这样就可以得到当前情况下每列进行操作能杀死的怪物。
我们用$c[i]$表示当前第$i$列进行操作后能杀死的怪物数量。排序一下选取最大值就好了。
容易想到$c[i]$很小，实际上我么用计数排序会更快。
#include <iostream> using namespace std; const int n = 20; int m; int a[25][25]; int c[25]; int ans; void DFS(int x, int cnt) { if(cnt >= m) return; int t[25] = {0}, tot = 0, tmp = m - cnt; for(register int i = 1; i <= n; ++i) { ++t[c[i]]; } for(register int i = n; i && tmp; --i) { if(t[i] <= tmp) { tot += t[i] * i; tmp -= t[i]; } else { tot += tmp * i; tmp = 0; } } ans = max(ans, tot); for(register int i = x; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { if(a[i][j]) ++c[j]; } DFS(i + 1, cnt + 1); for(register int j = 1; j <= n; ++j) { if(a[i][j]) --c[j]; } } return; } int main() { cin >> m; char ch; for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { cin >> ch; a[i][j] = ch == '#'; } } DFS(1, 0); cout << ans; return 0; }