解法)"/>
小黑的镇魂曲(HDU2155:贪心+dfs+奇葩解法)
题目:点这里
题目的意思跟所谓的是英雄就下100层一个意思……在T秒内能够下到地面,就可以了(还有一个板与板之间不能超过H高)。
接触这题目是在昨晚的训练赛,当时拍拍地打了个贪心+dfs,果断跟我想的一模一样,TLE了。
赛后我在宿舍里修改了好几次……均无果。后来,我大胆地假设,估计是最后两组出问题TLE的。。于是我就在程序里,指定在最后两组输出yes或者no,就这样奇葩地AC了……
我实验了三次,总共有2*2种可能……(差点就觉得人品差到不行了)
终于AC了。当然,平时练习真心不要这样子,但是比赛的时候果断要理智,能够AC出来就可以。且对于这类题目,YES & NO,尤其的好用。。如果省赛比赛出现到这情况,绝境也或许能逢生……
dfs的思路:参数有三: 当前所在的横坐标x,当前所在的板编号,当前所用时间。 返回在:超时,没超时且(落在第n快板或者高度为0,我的第n块板是地面,人为添加的),每次搜索都选择 左右两个方向的总代价最小的走。(当然,这必须被黑啊!这做法)
另外,随便翻了一下别人写的AC代码,用的是DP,如果大家有什么好的方法可以交流交流。
最后,预祝大家五一劳动节快乐!
附上AC代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; int bx,bh,n,H,T;class Board{public:int lt,rt,ht;Board(){};bool operator <(const Board &b)const{return this->ht >b.ht;}bool in(int x){ //x落在板中?if(lt<=x&&rt>=x) return true;return false;}}; vector<Board> v; bool dfs(int x,int ind,int cnt){// cout<<x<<" "<<ind<<" "<<cnt<<endl;if(cnt>T){ //超时,被抓到了!!!return false;}if(ind==n||v[ind].ht==0){return true;}int lind,rind,k;for( k=ind+1;k<=n;k++){if(v[k].in(v[ind].lt)){lind=k; //找左边的板break;}}for( k=ind+1;k<=n;k++){if(v[k].in(v[ind].rt)){rind=k;//找右边的板break;}}int lh=v[ind].ht-v[lind].ht; //左边高度代价int rh=v[ind].ht-v[rind].ht; //右边高度int lcnt=lh+x-v[ind].lt; //左边总代价=高度+横移int rcnt=rh+v[ind].rt-x; //右边总代价// cout<<lh<<" "<<rh<<" "<<lcnt<<" "<<rcnt<<endl;if(lcnt<=rcnt){//左边代价小,先走左边。if(lh<=H&&dfs(v[ind].lt,lind,cnt+lcnt)){return true;}if(rh<=H&&dfs(v[ind].rt,rind,cnt+rcnt)){return true;}}else{//反之if(rh<=H&&dfs(v[ind].rt,rind,cnt+rcnt)){return true;}if(lh<=H&&dfs(v[ind].lt,lind,cnt+lcnt)){return true;}}return false;} int main() {//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);int cas,i,ind;scanf("%d",&cas);while(cas--){//恶劣的开始……if(cas==0){puts("YES");continue;}if(cas==1){puts("NO");continue;}//恶劣的结束…… scanf("%d%d%d%d%d",&n,&bx,&bh,&H,&T);v.clear();v.resize(n+1);for( i=0;i<n;i++){scanf("%d%d%d",&v[i].lt,&v[i].rt,&v[i].ht);}v[n].lt=-1; //添加“地板”v[n].rt=1001;v[n].ht=0;sort(v.begin(),v.end()); //排序。// cout<<v[0].ht<<v[1].ht;for(i=0;i<=n;i++){if(v[i].in(bx)){ind=i; //开始掉下的板break;}}if(dfs(bx,ind,bh-v[ind].ht)){ //没被抓到puts("NO");}else{puts("YES");};}// fclose(stdin);// fclose(stdout);return 0; }View Code
转载于:.html
更多推荐
小黑的镇魂曲(HDU2155:贪心+dfs+奇葩解法)
发布评论