【BZOJ2059】Buying Feed 购买饲料
2018-09-01 05:37:50来源:博客园 阅读 ()
题面
约翰开车来到镇上,他要带V吨饲料回家。如果他的车上有X吨饲料,每公里就要花费X^2元,开车D公里就需要D* X^2元。约翰可以从N家商店购买饲料,所有商店都在一个坐标轴上,第i家店的位置是Xi,饲料的售价为每吨Ci元,库存为Fi。n≤500,k≤10000。
输入格式
第1行:三个整数 V,E,N
第2..N+12..N+1行:第i+1行的三个整数代表Xi?,Fi?,Ci? .
输出格式
一个整数,代表最小花费.
数据范围
1 ≤ V≤ 10000 , 1 ≤ E ≤ 500 , 1 ≤ N ≤ 500;
0 < Xi < E, 1 ≤ Fi ≤ 10000, 1 ≤ Ci ≤ 10^7
样例
2 5 3 3 1 2 4 1 2 1 1 1
9
思路
首先打一个2维dp,表示在第i个点拥有j个饲料需要至少多少钱。
sort一遍xi,然后三重循环dp,方程为dp[i][j]=min(dp[i][j],dp[i-1][j-k]+a[i].c*k+(a[i].x-a[i-1].x)*(j-k)*(j-k));
最后cout<<dp[n][v]+(e-a[n].x)*v*v<<endl;表示最后一个店到家的最少价格+1...n家店的最小价值(就是1...n的最小价值)
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{int x,f,c;}a[505]; 4 long long v,e,n,dp[505][10005]; 5 bool cmp(node p,node q){return p.x<q.x;} 6 inline int read(){ 7 int ret=0,f=1;char ch=getchar(); 8 while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();} 9 while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar(); 10 return ret*f; 11 } 12 int main(){ 13 freopen("d.in","r",stdin); 14 freopen("d.out","w",stdout); 15 v=read();e=read();n=read(); 16 memset(dp,0x7f,sizeof(dp)); 17 for (int i=1;i<=n;i++) a[i].x=read(),a[i].f=read(),a[i].c=read(); 18 sort(a+1,a+n+1,cmp); 19 dp[0][0]=0; 20 for (int i=1;i<=n;i++) 21 for (int j=0;j<=v;j++) 22 for (int k=0;k<=a[i].f&&k<=j;k++) 23 dp[i][j]=min(dp[i][j],dp[i-1][j-k]+a[i].c*k+(a[i].x-a[i-1].x)*(j-k)*(j-k)); 24 cout<<dp[n][v]+(e-a[n].x)*v*v<<endl; 25 return 0; 26 }
可惜以上方法会炸
那就让我们来优化吧:首先把家当做一个店,距离为e,库存为0,单价为0.
然后用一个deque存k.
如果(j-q.front() > a[i-1].f)就pop掉队首, 因为i-1的店库存不够;
如果top=q.back(), dp[i-1][top]-a[i-1].c*top>=dp[i-1][j]-w[i-1]*j, 就pop掉队尾;
过程中有可能爆int,所以开long long。
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{long long x,f,c;}a[505]; 4 long long v,e,n,dp[505][10005]; 5 bool cmp(node p,node q){return p.x<q.x;} 6 int main(){ 7 freopen("d.in","r",stdin); 8 freopen("d.out","w",stdout); 9 cin>>v>>e>>n; 10 memset(dp,0x7f,sizeof(dp)); 11 for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].f>>a[i].c; 12 n++; 13 a[n]=(node){e,0,0}; 14 sort(a+1,a+n+1,cmp); 15 dp[0][0]=0; 16 for (int i=1;i<=n;i++) 17 { 18 deque<long long>q; 19 for (int j=0;j<=v;j++) 20 { 21 while (!q.empty()&&j-q.front()>a[i-1].f) q.pop_front(); 22 if (dp[i-1][j]!=0x7f) 23 { 24 while (!q.empty()&&dp[i-1][q.back()]-a[i-1].c*q.back()>=dp[i-1][j]-a[i-1].c*j) q.pop_back(); 25 q.push_back(j); 26 } 27 int top=q.front(); 28 if (!q.empty()) dp[i][j]=dp[i-1][top]-a[i-1].c*top+(a[i].x-a[i-1].x)*j*j+a[i-1].c*j; 29 } 30 } 31 cout<<dp[n][v]<<endl; 32 return 0; 33 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash