CF6D Lizards and Basements 2题解

CF6D Lizards and Basements 2

题意：有n个人，编号1到n，每个人有血量$h_i$对某个人攻击会产生a点伤害，会波及到相邻的人，对相邻的人产生b点伤害（1和n号人不能攻击），问最少要攻击多少次才能让所有人的h小于0，分别攻击了谁。

解法：dfs搜索，先处理出每个人最多攻击多少次，对攻击次数枚举，每次保证当前点前所有人h值已经小于0。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, a, b, h[N], ci[N], tmp[N];
int res = 1e9, r[N];
void dfs(int step, int ans) {
    
	
	if(ans >= res) return ;
	
// cout << step << endl;
	if(step == n) {
    
// cout << ans << " " << res << " " << h[n] << endl;
		if(h[n] < 0) {
    
			if(ans < res) {
    
				for(int i = 2; i <= step; ++i) r[i] = tmp[i];
				res = ans;
			}
		}
		return;
	}
	for(int i = 0; i <= ci[step]; ++i) {
    
		if(i*b <= h[step-1]) continue;
		tmp[step] = i;
		h[step+1] -= i*b;
		h[step] -= i*a;
		
		dfs(step+1, ans+i);
		
		h[step+1] += i*b;
		h[step] += i*a;
		tmp[step] = 0;
	}
}
int main() {
    
	scanf("%d%d%d", &n, &a, &b);
	for(int i = 1; i <= n; ++i) scanf("%d", &h[i]); 
	for(int i = 2; i < n; ++i) {
    
		ci[i] = max(h[i]/a, max(h[i-1]/b, h[i+1]/b)) + 1;
	}
	dfs(2, 0);
	printf("%d\n", res);
	for(int i = 2; i < n; ++i) 
		for(int j = 0; j < r[i]; ++j) printf("%d ", i);
	puts("");
	return 0;
}