首页 > 其他 > 详细

bzoj1617[Usaco2008 Mar]River Crossing渡河问题*

时间:2016-08-06 15:40:36      阅读:258      评论:0      收藏:0      [点我收藏+]

bzoj1617[Usaco2008 Mar]River Crossing渡河问题

题意:

一个人和n牛渡河,人载i头牛渡河所需时间为m+sigma(j,1,i)a[j],人不载牛所需时间为m,到了对岸如果还要载牛必须花时间m把船开回来。问最短时间。n≤2500

题解:

dp。f[i][j]=min(f[i+1][j+1]+a[j+1],f[i+1][0]+a[j+1]+m*2),最后答案为f[1][0]+m。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 3000
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define dec(i,j,k) for(int i=j;i>=k;i--)
 7 using namespace std;
 8 
 9 inline int read(){
10     char ch=getchar(); int f=1,x=0;
11     while(ch<0||ch>9){if(ch==-)f=-1; ch=getchar();}
12     while(ch>=0&&ch<=9)x=x*10+ch-0,ch=getchar();
13     return f*x;
14 }
15 int n,m,a[maxn],x[maxn],y[maxn];
16 int main(){
17     n=read(); m=read(); inc(i,1,n)a[i]=read();
18     dec(i,n,1){
19         memset(y,0,sizeof(y)); inc(j,0,i)y[j]=min(x[j+1]+a[j+1],x[0]+a[j+1]+m*2); swap(x,y);
20     }
21     printf("%d",x[0]+m); return 0;
22 }

 

20160803

bzoj1617[Usaco2008 Mar]River Crossing渡河问题*

原文:http://www.cnblogs.com/YuanZiming/p/5743977.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!