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

 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 }