nyoj30Gofinishing经典贪心

题目地址

话说&＃xff0c;这个题从去年就想写了。解题报告都看了不知道多少遍&＃xff0c;一直没能写出来(鄙视一下自己)。今天下了决心一定要写出来&＃xff0c;果然、、、、花了一番心思后&＃xff0c;终于AC啦&＃xff01;啦啦啦 嘿嘿 。。。吖飒&＃xff01;加油~~~~

题意(英文题&＃xff0c;当初翻译了好久才明白题意&＃xff0c;痛心呀&＃xff0c;My English)&＃xff1a;

佳佳去钓鱼&＃xff0c;池塘在一条直线上&＃xff0c;每个池塘能钓到的鱼按di递减&＃xff0c;从池塘i到i&＃43;1需要ti的时间。问佳佳最多能钓到的鱼。如果在池塘1和在池塘i&＃43;1钓的鱼数目一致&＃xff0c;则佳佳就呆在池塘1。

分析&＃xff1a;

大致的看看&＃xff0c;并不能发现它是个贪心&＃xff0c;或者&＃xff0c;尽管知道它是贪心&＃xff0c;并不能很好的分析出它的做题思路。

每个池塘能钓到的鱼数是递减的&＃xff0c;从池塘i到i&＃43;1需要ti的时间。那么就可以&＃xff0c;总时间先减去奔波各个池塘的时间。那么&＃xff0c;就可以真正的贪心了&＃xff08;解题报告上就这一句话&＃xff09;。

如何贪心呢&＃xff1f;今天才算知道、、、、、

因为会出现&＃xff1a;最后j个池塘不值得去&＃xff08;路上花的时间不如去钓到别的池塘的鱼&＃xff09;&＃xff0c;解决这种冲突的办法就是&＃xff0c;从前往后&＃xff0c;搜索只去前i个池塘的Maxfish&＃xff0c;记录最大Maxfish就是所求。至于在每个池塘所呆的时间&＃xff0c;需要每次找到最优的Maxfish都更新一下。另外&＃xff0c;把最后剩余的时间全部送给T[1]

#include
#include
using namespace std;
struct fish
{int f;int d;int t;
}N[26];
int T[26];//每个湖停留的时间
int temp[26];
int Maxfish;int Troad;
int scheme(int n,int h)//前n个湖的最优方案
{int i;int troad&＃61;0;int sum&＃61;0;int tt[26]&＃61;{0};memset(tt,0,sizeof(tt));for(i&＃61;1;i0){//找鱼最多的湖int m&＃61;0;int p;int flag&＃61;0;for (i&＃61;1;i<&＃61;n;i&＃43;&＃43;) if(N[i].f>m) {m&＃61;N[i].f;p&＃61;i;flag&＃61;1;}if(flag&＃61;&＃61;0) break;sum&＃43;&＃61;m;tt[p]&＃43;&＃43;;N[p].f-&＃61;N[p].d;h--;}if(h>0) tt[1]&＃43;&＃61;h;if(Maxfish}
int main()
{int i,j;int n;//湖的数量while(cin>>n&&n!&＃61;0){Maxfish&＃61;0;memset(N,0,sizeof(N));memset(T,0,sizeof(T));//忘记初始化&＃xff0c;WA了两次。int h;cin>>h;//总的时间h*&＃61;12;for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cin>>N[i].f;//最开始能钓到的鱼数for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cin>>N[i].d;//每分钟的减少量for(i&＃61;1;i>N[i].t;//从i到i&＃43;1需要的时间间隔//计算Maxfish及T[i]for (i&＃61;1;i<&＃61;n;i&＃43;&＃43;)//找最优方案{for(j&＃61;1;j<&＃61;n;j&＃43;&＃43;)temp[j]&＃61;N[j].f;scheme(i,h);for(j&＃61;1;j<&＃61;n;j&＃43;&＃43;)N[j].f&＃61;temp[j];}//print resultfor(i&＃61;1;i}