首页 > 代码库 > vijos1623开心农场(HOI)
vijos1623开心农场(HOI)
题目:https://vijos.org/p/1623
解:
其实我们可以发现有几块土地,和这道题目根本没什么关系,一种植物肯定比多种植物要优,所以我们就当一块土地来做,最后再把钱乘以土地数量就好了。
然后就是一个和背包很像的动归加个二分,在程序注释里解释好了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,t,k,a[5009],ti[5009],p[5009],f[5009]; int find(int x) //二分找时间 { int l=0,r=k,ans=0; while (l<=r) { int mid=(l+r)/2; if (a[mid]<=x) { ans=mid; l=mid+1; } else r=mid-1; } return ans; } int main() { scanf("%d%d%d%d",&n,&m,&t,&k); int x,y; for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&ti[i],&y); p[i]=y-x;//每种植物能赚的钱 } for (int i=1;i<=k;i++) scanf("%d",&a[i]); sort(a+1,a+1+k); //这里一定要排序,因为输入的时间不一定有序 f[1]=0; //f[i]表示第i次上线时能赚的最多的钱 for (int i=2;i<=k;i++) { for (int j=1;j<=m;j++) if (a[i]-ti[j]>=0) { int now=find(a[i]-ti[j]); //找到如果要在第i次上线时收获j这种植物,那么最迟要在第now次种下 if (now==0) continue; //如果没法上线,就退出 f[i]=max(f[i],f[now]+p[j]); //更新答案 } } printf("%d\n",f[k]*n); return 0; }
vijos1623开心农场(HOI)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。