怎么做企业网站教程视频,青岛市城市建设投标网站,腾讯企业邮箱登陆入口,网站换域名 百度收录前言
上篇#xff1a;纯贪心做法 下篇#xff1a;dp做法 题目#xff1a;OJ1373 正题
有N个鱼塘#xff0c;给出每分钟可以钓到的鱼数和每钓一次下一次钓减少的鱼数和到下一个鱼塘需要几分钟#xff08;不能回头#xff09;。求限定时间内最多能够钓到的鱼数 解题思路…前言
上篇纯贪心做法 下篇dp做法 题目OJ1373 正题
有N个鱼塘给出每分钟可以钓到的鱼数和每钓一次下一次钓减少的鱼数和到下一个鱼塘需要几分钟不能回头。求限定时间内最多能够钓到的鱼数 解题思路
由于是贪心优化所以引用一下上篇的贪心 由于数据较小我们枚举一下最后到达的池塘然后在开始计算时间时就减去路程然后就可以在计算时不需要计算路程问题了。然后每次找最多鱼的池塘钓然后减那个池塘的鱼数这里讲一下原理由于我们不能确定这时是继续钓好还是去下一个池塘钓好于是我们就用这种方法确定每个池塘应该钓多久以此类推直到时间耗尽然后每次更新最大答案。 开一个大根堆每次用堆来快速确定最大值。 代码
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
struct water{int fish,number;//记录鱼塘鱼数和编号
};
water a[101];
int tn,lt,num[101],t[101],mov[101],sum,n,m;
void up(int x)//维护堆
{while (x1 a[x].fisha[x/2].fish){swap(a[x],a[x/2]);x/2;}
}
void down(int x)//维护堆
{int y;while (x*2tn a[x].fisha[x*2].fish || x*21tn a[x].fisha[x*21].fish){yx*2;if (x*21tn a[y].fisha[y1].fish) y;swap(a[x],a[y]);xy;}
}
int main()
{scanf(%d,n);for (int i1;in;i) scanf(%d,num[i]);for (int i1;in;i) scanf(%d,mov[i]);for (int i1;in;i) scanf(%d,t[i]);scanf(%d,m);for (int k1;kn;k){int timem-lt,ans0;tn0;for (int i1;ik;i){a[tn].fishnum[i];a[tn].numberi;//建堆up(tn);//维护}while (time0 a[1].fish0)//时间耗尽或每鱼了{ansa[1].fish;//钓a[1].fish-mov[a[1].number];//减去down(1);//维护堆time--;//消耗时间}summax(sum,ans);//h更新最大值ltt[k];//提前计算路程}printf(%d,sum);
}
