bzoj1742[Usaco2005 nov]Grazing on the Run 边跑边吃草*&&bzoj3074[Usaco2013 Mar]The Cow Run*

bzoj1742[Usaco2005 nov]Grazing on the Run 边跑边吃草&&bzoj3074[Usaco2013 Mar]The Cow Run

bzoj1742[Usaco2005 nov]Grazing on the Run 边跑边吃草

bzoj3074[Usaco2013 Mar]The Cow Run

题意：

数轴上有n棵草，牛初始在L位置（bzoj3074的牛初始在1位置），每移动一个单位需要+1s。而每过1s没吃的草腐败度会+1，问吃完所有草的最小腐败度。n≤1000。

题解：

很神的dp。f[l][r][0/1]表示从第l棵草吃到第r棵草，之后到达l/r。则

f[l][r][0]=min(dfs(l+1,r,0)+(n-r+l)*(a[l+1]-a[l]),dfs(l+1,r,1)+(n-r+l)*(a[r]-a[l]));
f[l][r][1]=min(dfs(l,r-1,1)+(n-r+l)*(a[r]-a[r-1]),dfs(l,r-1,0)+(n-r+l)*(a[r]-a[l]));

之所以要乘(n-r+l)的原因是在当前的转移的同时所有未吃的草的腐败度都增加了等同于当前转移时间的值。

为了方便处理，先增加一棵虚拟的草位置为l，接下来设除了虚拟的草所有f[i][i]为正无穷，而那棵虚拟的草对于的f[i][i]=0。

代码（bzoj1742）：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 1010
 7 #define ll long long
 8 #define INF 1e16
 9 using namespace std;
10 
11 inline int read(){
12     char ch=getchar(); int f=1,x=0;
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
14     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
15     return f*x;
16 }
17 ll f[maxn][maxn][2]; int a[maxn],n,l;
18 ll dfs(int l,int r,int b){
19     if(f[l][r][b]!=-1)return f[l][r][b];
20     if(!b)f[l][r][b]=min(dfs(l+1,r,0)+(n-r+l)*(a[l+1]-a[l]),dfs(l+1,r,1)+(n-r+l)*(a[r]-a[l]));
21     else f[l][r][b]=min(dfs(l,r-1,1)+(n-r+l)*(a[r]-a[r-1]),dfs(l,r-1,0)+(n-r+l)*(a[r]-a[l]));
22     return f[l][r][b];
23 }
24 int main(){
25     n=read(); l=read(); memset(f,-1,sizeof(f));
26     inc(i,1,n)a[i]=read(); a[++n]=l; sort(a+1,a+n+1); inc(i,1,n)f[i][i][0]=f[i][i][1]=INF;
27     inc(i,1,n)if(a[i]==l){f[i][i][0]=f[i][i][1]=0; break;}
28     printf("%lld",min(dfs(1,n,0),dfs(1,n,1))); return 0;
29 }

20161019