Cf6d lizards and fundamentals 2 problem solving

CF6D Lizards and Basements 2

The question ： Yes n personal , Number 1 To n, Everyone has blood $h_i$ An attack on someone can have a Point injury , It will affect the neighboring people , Have an impact on the neighbors b Point injury （1 and n No one can attack ）, Ask how many times you must attack at least to make everyone h Less than 0, Who were attacked .

solution ：dfs Search for , First deal with the maximum number of attacks each person can make , Enumerate the number of attacks , Ensure that everyone before the current point every time h The value is already less than 0.

Code ：

#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;
}