Codeforces 6D Lizards and Basements 2 dfs+暴力

题目链接:点击打开链接

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<set>
#include<vector>
#include<map>
#include<math.h>
#include<queue>
#include<string>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 110
#define ll int ll n, a, b;
ll h[N];
vector<int>G,ans;
void dfs(int u, bool hehe){//hehe=true表示u-1没死
if(u==n && hehe==false){
if(G.size()<ans.size())
ans = G;
return ;
}
int siz = 0;
if(hehe) {
while(h[u-1]>0)siz++,h[u-1]-=b, h[u]-=a, h[u+1]-=b, G.push_back(u);
}
if(h[u]>0) {
while(h[u]>0) {
dfs(u+1,true);
h[u-1]-=b;
h[u]-=a;
h[u+1]-=b;
siz++;
G.push_back(u);
}
}
dfs(u+1,false);
h[u]+=a*siz;
h[u+1]+=b*siz;
h[u-1]+=b*siz;
while(siz--)G.erase(G.end()-1);
}
int main(){
ll i, j;
while(~scanf("%d %d %d",&n,&a,&b)){
G.clear(); ans.clear();
for(i=1;i<=n;i++)scanf("%d",&h[i]), h[i]++;
while(h[1]>0){
h[2] -= a;
h[1] -= b;
h[3] -= b;
ans.push_back(2);
}
while(h[n]>0){
h[n-2] -= b;
h[n-1] -= a;
h[n] -= b;
ans.push_back(n-1);
}
G = ans;
for(i=1;i<=100;i++)ans.push_back(i);
dfs(2,false);
printf("%d\n",ans.size());
for(i = 0; i < ans.size(); i++)printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
}
return 0;
} /**/
上一篇:C#中MD5加密


下一篇:福州大学第十六届程序设计竞赛