首页 > 代码库 > Codeforces 6D Lizards and Basements 2 dfs+暴力
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; } /**/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。