本文共 3307 字，大约阅读时间需要 11 分钟。
简单区间DP学完了，自己独立做道区间DP的题目，居然最大值计算错了，导致n遍wrong answer
庆幸的是这次除了这点错误外，状态转移是完全正确的，还得继续做，。。。
1、
2、题目大意：
有n块草坪，知道每块草坪的位置（我们可以看做是x轴上的一点），Bessie位于L位置，他可以向左右两个方向去吃草坪，假设吃草坪的时间不计，路上的时间是每走一个单位，时间+1，每块草坪都有一个staleness值，这个值恰好等于Bessie到达的时间，现在要求的是Bessie将所有草坪吃完，所有草坪的staleness值最小是多少，例如样例
4 10191119
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 #include #include using namespace std;#define N 10005#define INF 1000000009int a[N],b[N];int dp[N][N][2];int cmp(int a,int b){ return a >1; if(a[m]==key) return m; if(key =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 #include #include using namespace std;#define N 10005#define INF 1<<30int a[N],b[N];int dp[N][N][2];int cmp(int a,int b){ return a >1; if(a[m]==key) return m; if(key =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;}
转载地址：http://vwcdi.baihongyu.com/