湖北皇奥建设工程有限公司网站,新浪微博网页版,网站浏览历史能恢复吗怎么设置,wordpress 仿美文前言
上篇#xff1a; 纯贪心做法 堆优化贪心
题目#xff1a;OJ1373 正题
有N个鱼塘#xff0c;给出每分钟可以钓到的鱼数和每钓一次下一次钓减少的鱼数和到下一个鱼塘需要几分钟#xff08;不能回头#xff09;。求限定时间内最多能够钓到的鱼数 解题思路
用f[i][…前言
上篇 纯贪心做法 堆优化贪心
题目OJ1373 正题
有N个鱼塘给出每分钟可以钓到的鱼数和每钓一次下一次钓减少的鱼数和到下一个鱼塘需要几分钟不能回头。求限定时间内最多能够钓到的鱼数 解题思路
用f[i][j]表示在第i个鱼塘第j分钟时最多能钓到的鱼数。然后推出递推方程
f[i][j]max(f[i−1][j−k−t[i−1]]s)f[i][j]max(f[i−1][j−k−t[i−1]]s)
f[i][j]=max(f[i-1][j-k-t[i-1]]+s) j-k-t[i]表示去除路程后在当前鱼塘钓k分钟然后枚举一下ks表示在当前鱼塘钓k分钟能得到的余数 时间复杂度O(n*m^2)代码
#includeiostream
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int lt,num[101],t[101],mov[101],sum,n,m,s[101],r;
int f[101][1001];
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);//输入memset(f,-1,sizeof(f));//初始化f[0][0]0;//初始化,toofor (int i1;in;i){f[i][0]0;//依旧是初始化r0;s[0]0;//仍然是初始化while (ltrm num[i]0){r;s[r]s[r-1]num[i];num[i]-mov[i];}//计算待到几分钟的钓鱼数其实可以用公式求for (int j1;jm;j){for (int k0;kj-lt;k){if (j-k-lt0) break;//退出循环if (f[i-1][j-k-t[i-1]]!-1)f[i][j]max(f[i][j],f[i-1][j-k-t[i-1]]s[min(k,r)]);//动态转移}summax(sum,f[i][j]);//更新最优解}ltt[i];//提前计算路程}printf(%d,sum);//输出
}
