题解

记录一下我拿下了 cf *2600 的题目吧。

思路分析：

注意到题目的数据范围很小，这你想不到暴力 $DFS$ 吗，最朴素的思路就是枚举最小的攻击次数，然后再使用 $DFS$ 跑一遍，这应该都能想到吧。但是你会发现这种 枚举然后 $DFS$ 的做法会超时一点，所以这个时候就可以想到剪枝，但是如何剪枝呢，就是枚举当前这个人打不打的时候，如果左边的人都没有打完，那就必须先打完左边的，所以当前的那个必须选。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define clear1 for(int i=1;i<=n;i++)b[i]=a[i]
#define clear2 ans.clear()
const int N=57;
int n,aa,bb;
int a[N],b[N];
bool mp[N],flag=false;
vector<int>ans;
bool check(){
	for(int i=1;i<=n;i++) if(b[i]>=0) return false;
	return true;
}
void dfs(int start,int time,int allow){
	if(flag) return ;
	if(time>allow) return;
	if(check()){flag=true;return;}
	if(start>n) return;
	if(start>1&&b[start-1]>=0){
		if(start!=1&&start!=n){
			if(flag) return;
			b[start]-=aa,b[start-1]-=bb,b[start+1]-=bb;
			ans.push_back(start);
			dfs(start,time+1,allow);
			if(flag) return;
			b[start]+=aa,b[start-1]+=bb,b[start+1]+=bb;
			ans.pop_back();
		}
		return;
	}
	//这里分为两种选择
	//1.不选当前的
	dfs(start+1,time,allow);
	if(start!=1&&start!=n){
		if(flag) return;
		//2.选当前的
		b[start]-=aa,b[start-1]-=bb,b[start+1]-=bb;
		//数组加入选择的 
		ans.push_back(start);
		dfs(start,time+1,allow);
		if(flag) return;
		b[start]+=aa,b[start-1]+=bb,b[start+1]+=bb;
		ans.pop_back();
	}
}
int main(){
	cin>>n>>aa>>bb;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=100;i++){
		clear1; clear2; flag=false;
		dfs(2,0,i);
		if(flag){
			cout<<i<<endl;
			for(int x:ans) cout<<x<<' ';
			break;
		}
	}
	return 0;
}