简单区间DP学完了，自己独立做道区间DP的题目，居然最大值计算错了，导致n遍wrong answer
庆幸的是这次除了这点错误外，状态转移是完全正确的，还得继续做，。。。
1、http://poj.org/problem?id=3042
2、题目大意：
有n块草坪，知道每块草坪的位置（我们可以看做是x轴上的一点），Bessie位于L位置，他可以向左右两个方向去吃草坪，假设吃草坪的时间不计，路上的时间是每走一个单位，时间+1，每块草坪都有一个staleness值，这个值恰好等于Bessie到达的时间，现在要求的是Bessie将所有草坪吃完，所有草坪的staleness值最小是多少，例如样例
4 10 1 9 11 19
Bessie can follow this route:
* start at position 10 at time 0
* move to position 9, arriving at time 1
* move to position 11, arriving at time 3
* move to position 19, arriving at time 11
* move to position 1, arriving at time 29
所以所有草坪最小的staleness值就是1+3+11+29=44
3、思路分析
这是一道区间DP的问题，我们用dp[i][j][0]表示从i-j区间都吃完，最后停留在i位置，所有草坪的最小的staleness值
dp[i][j][1]表示i-j区间都吃完，最后停留在j位置上的最小值
那么这两个状态的转移方程就是
dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1]-a[i])*(delay+b[i]));
dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j]-a[i])*(delay+b[i]));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j]-a[j-1])*(delay+b[j]));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j]-a[i])*(delay+b[j]));
对于这道题目来说每个草坪的初始staleness值假设都是1，那么Bessie所在的位置的staleness值就是0，我们用一个数组b[]来记录
这道题目也可以不用这样做，直接delay=n-(j-i),就不用加上b[],网上有人的代码是这么做的，尚不太理解
4、AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 10005
#define INF 1000000009
int a[N],b[N];
int dp[N][N][2];
int cmp(int a,int b)
{return a<b;
}
int binarySearch(int l,int r,int key)
{while(l<=r){int m=(l+r)>>1;if(a[m]==key)return m;if(key<a[m])r=m-1;elsel=m+1;}return 0;
}
void DP(int p,int n)
{for(int i=1;i<=n;i++)b[i]=1;b[p]=0;for(int i=0; i<=n; i++){for(int j=0; j<=n; j++){dp[i][j][0]=INF;dp[i][j][1]=INF;}}dp[p][p][0]=dp[p][p][1]=0;for(int i=p; i>=1; i--){for(int j=p; j<=n; j++){if(i==j)continue;int delay=n-(j-i+1);// printf("&%d %d %d\n",i,j,delay);dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1]-a[i])*(delay+b[i]));dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j]-a[i])*(delay+b[i]));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j]-a[j-1])*(delay+b[j]));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j]-a[i])*(delay+b[j]));}}
}
int main()
{int n,l;scanf("%d%d",&n,&l);for(int i=1; i<=n; i++){scanf("%d",&a[i]);}a[n+1]=l;sort(a+1,a+n+2,cmp);int ans=binarySearch(1,n+1,l);//printf("ans=%d\n",ans);DP(ans,n+1);int ret=min(dp[1][n+1][0],dp[1][n+1][1]);printf("%d\n",ret);return 0;
}
不用b[]数组的AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 10005
#define INF 1<<30
int a[N],b[N];
int dp[N][N][2];
int cmp(int a,int b)
{return a<b;
}
int binarySearch(int l,int r,int key)
{while(l<=r){int m=(l+r)>>1;if(a[m]==key)return m;if(key<a[m])r=m-1;elsel=m+1;}return 0;
}
void DP(int p,int n)
{for(int i=1;i<=n;i++)b[i]=1;b[p]=0;for(int i=0; i<=n; i++){for(int j=0; j<=n; j++){dp[i][j][0]=INF;dp[i][j][1]=INF;}}dp[p][p][0]=dp[p][p][1]=0;for(int i=p; i>=1; i--){for(int j=p; j<=n; j++){if(i==j)continue;//如果delay这样定义，就不用b[]int delay=n-j+i;// printf("&%d %d %d\n",i,j,delay);dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1]-a[i])*(delay));dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j]-a[i])*(delay));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j]-a[j-1])*(delay));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j]-a[i])*(delay));}}
}
int main()
{int n,l;scanf("%d%d",&n,&l);for(int i=1; i<=n; i++){scanf("%d",&a[i]);}a[n+1]=l;sort(a+1,a+n+2,cmp);int ans=binarySearch(1,n+1,l);//printf("ans=%d\n",ans);DP(ans,n+1);int ret=min(dp[1][n+1][0],dp[1][n+1][1]);printf("%d\n",ret);return 0;
}