在刷ZeroClock大神的区间DP专辑，遇见了ZOJ3469，完全不无从下手，然后有人说是论问题，推荐看徐源盛《对一类动态规划问题的研究》这篇论文，果断得膜拜了下，感觉好神奇，可以把未来的费用提前计算好~~~顺便把相关的三道题A了，其实都是一样的。。。
BZOJ2037 [Sdoi2008]Sue的小球
题目大意
中文的。。。
题解
这是论文的例题
直接上原文的讲解吧。。。
把dp数组初始化为0x7fffffffWA了，改成0x3f3f3f3f就AC了。。。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
using namespace std;
#define MAXN 1005
#define INF 0x3f3f3f3f
int dp[2][MAXN][MAXN];
int sum[MAXN];
bool visit[MAXN][MAXN];
int n,x0;
typedef struct
{
int x,y,v;
} NODE;
NODE a[MAXN];
bool cmp(const NODE a,const NODE b)
{
return a.x<b.x;
}
void dfs(int l,int r)
{
if(visit[l][r]) return;
if(l==r)
{
if(a[r].x==x0)
dp[0][l][r]=dp[1][l][r]=0;
else dp[0][l][r]=dp[1][l][r]=-INF;
return;
}
visit[l][r]=1;
dfs(l+1,r);
dfs(l,r-1);
dp[0][l][r]=a[l].y+max(dp[0][l+1][r]-(a[l+1].x-a[l].x)*(sum[n]-sum[r]+sum[l]),
dp[1][l+1][r]-(a[r].x-a[l].x)*(sum[n]-sum[r]+sum[l]));
dp[1][l][r]=a[r].y+max(dp[1][l][r-1]-(a[r].x-a[r-1].x)*(sum[n]-sum[r-1]+sum[l-1]),
dp[0][l][r-1]-(a[r].x-a[l].x)*(sum[n]-sum[r-1]+sum[l-1]));
return;
}
int main()
{
scanf("%d%d",&n,&x0);
for(int i=1; i<=n; i++)
scanf("%d",&a[i].x);
for(int i=1; i<=n; i++)
scanf("%d",&a[i].y);
for(int i=1; i<=n; i++)
scanf("%d",&a[i].v);
a[++n].x=x0;
sort(a+1,a+n+1,cmp);
sum[0]=0;
for(int i=1; i<=n; i++)
sum[i]=sum[i-1]+a[i].v;
dfs(1,n);
printf("%.3lf\n",(double)(max(dp[0][1][n],dp[1][1][n]))/1000.0);
return 0;
}
POJ3042 Grazing on the Run
题目大意
在X坐标轴上有n堆草，有一条牛的初始位置是在坐标L，牛(移动速度为1个单位/s)每次可以向左或者向右把一堆草吃掉，每堆草有一个腐烂度，它的值等于牛从开始到吃它位置的时间，牛想把所有草吃完之后，腐烂值的总和最小
题解
先对坐标进行排序，然后就进行DP，方程和BZOJ2037是一样的~~~
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 1005
int dp[2][MAXN][MAXN];
int x[MAXN];
int n,x0;
int main()
{
scanf("%d%d",&n,&x0);
for(int i=1;i<=n;i++)
scanf("%d",&x[i]);
x[++n]=x0;
sort(x+1,x+n+1);
for(int i=1;i<=n;i++)
if(x[i]!=x0)dp[0][i][i]=dp[1][i][i]=INF;
else
dp[0][i][i]=dp[1][i][i]=0;
for(int i=n;i>=1;i--)
for(int j=i+1;j<=n;j++)
{
dp[0][i][j]=min(dp[0][i+1][j]+(x[i+1]-x[i])*(n-j+i),
dp[1][i+1][j]+(x[j]-x[i])*(n-j+i));
dp[1][i][j]=min(dp[1][i][j-1]+(x[j]-x[j-1])*(n-j+i),
dp[0][i][j-1]+(x[j]-x[i])*(n-j+i));
}
printf("%d\n",min(dp[0][1][n],dp[1][1][n]));
return 0;
}
ZOJ3469 Food Delivery
题目大意
和上题没啥区别。。。
有n个人叫餐，每个人都在x轴上，并且每个人都有个坑爹度(和等餐时间有关，据说顾客认为坑爹值到一定程度他的小宇宙就要爆发).现在送餐员从x轴上的某点出发，路上奔跑速度是v，要一次性把所有餐送完。叫餐的人得到餐的时间和顺序不同，坑爹度总和也就不同
题解
同上。。。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 1005
#define x first
#define y second
#define INF 0x3f3f3f3f
int dp[2][MAXN][MAXN];
int sum[MAXN];
bool visit[MAXN][MAXN];
pair<int,int>a[MAXN];
int n,v,x0;
void dfs(int l,int r)
{
if(visit[l][r]) return;
if(l==r)
{
if(a[l].x==x0)dp[0][l][r]=dp[1][l][r]=0;
else
dp[0][l][r]=dp[1][l][r]=INF;
return;
}
visit[l][r]=true;
dfs(l+1,r);
dfs(l,r-1);
dp[0][l][r]=min(dp[0][l+1][r]+(a[l+1].x-a[l].x)*(sum[n]-sum[r]+sum[l]),
dp[1][l+1][r]+(a[r].x-a[l].x)*(sum[n]-sum[r]+sum[l]));
dp[1][l][r]=min(dp[1][l][r-1]+(a[r].x-a[r-1].x)*(sum[n]-sum[r-1]+sum[l-1]),
dp[0][l][r-1]+(a[r].x-a[l].x)*(sum[n]-sum[r-1]+sum[l-1]));
}
int main()
{
while(scanf("%d%d%d",&n,&v,&x0)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
a[++n].x=x0;
a[n].y=0;
sort(a+1,a+n+1);
sum[0]=0;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i].y;
memset(visit,false,sizeof(visit));
dfs(1,n);
printf("%d\n",v*min(dp[0][1][n],dp[1][1][n]));
}
return 0;
}