ZOJ 3469 Food Delivery

区间DP。

首先很容易想到送货顺序是起点不断向两边扩展的。这样可以用区间DP做。

但是，如果我们这样设计dp，dp[i][j][X]表示[i,j]这一段区间都送完，最终在左端点、右端点的最小花费，是有后效性的。

为什么有后效性？ 如果有一种方案得到的dp[5][8][0]较小，但走的总路程较多，另一种得到的dp[5][8][0]较大，但是总路程很小，这样不能确定哪一种往后推得到的答案更小！

正确的DP是这样设计的：dp[i][j][X]表示[i,j]这段区间都送完，最后在哪一个端点，对所有人造成的花费的最小值，即还要加上没有收到货物的那群人已经产生的花费。

状态转移方程很容易写：

dp[st][en][0]=min(
　　dp[st+1][en][0]+abs(s[st+1].x-s[st].x)*(sum_now+s[st].b)*V,
　　dp[st+1][en][1]+abs(s[en].x-s[st].x)*(sum_now+s[st].b)*V
);

dp[st][en][1]=min(
　　dp[st][en-1][1]+abs(s[en].x-s[en-1].x)*(sum_now+s[en].b)*V,
　　dp[st][en-1][0]+abs(s[en].x-s[st].x)*(sum_now+s[en].b)*V
);

注意：开longlong，虽然题目说答案不会超int，但中间过程好像会超......

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=1000+10;
const int INF=0x7FFFFFFF;
int n;
long long V,X;
struct LOVE
{
    long long  x;
    long long  b;
}s[maxn];
bool cmp(const LOVE&a,const LOVE&b)
{
    return a.x<b.x;
}

long long dp[maxn][maxn][2];
long long sum[maxn];

void read()
{
    for(int i=1;i<=n;i++) scanf("%lld%lld",&s[i].x,&s[i].b);
}

void work()
{
    sort(s+1,s+1+n,cmp);

    memset(sum,0,sizeof sum);
    for(int i=1;i<=n;i++) sum[i]=s[i].b+sum[i-1];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j][0]=dp[i][j][1]=INF;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int st=j,en=st+i-1;
            if(en>n) continue;
            if(i==1)
            {
                dp[st][en][0]=dp[st][en][1]=(sum[n]-sum[0])*abs(s[st].x-X)*V;
                continue;
            }

            int sum_now=0;
            if(st-1>=1) sum_now=sum_now+sum[st-1]-sum[0];
            if(n>=en+1) sum_now=sum_now+sum[n]-sum[en];
            dp[st][en][0]=min(
                              dp[st+1][en][0]+abs(s[st+1].x-s[st].x)*(sum_now+s[st].b)*V,
                              dp[st+1][en][1]+abs(s[en].x-s[st].x)*(sum_now+s[st].b)*V
                              );

            dp[st][en][1]=min(
                              dp[st][en-1][1]+abs(s[en].x-s[en-1].x)*(sum_now+s[en].b)*V,
                              dp[st][en-1][0]+abs(s[en].x-s[st].x)*(sum_now+s[en].b)*V
                              );
        }
    }

    printf("%lld
",min(dp[1][n][0],dp[1][n][1]));
}

int main()
{
    while(~scanf("%d%lld%lld",&n,&V,&X))
    {
        read();
        work();
    }
    return 0;
}