ZOJ 3469 Food Delivery 区间DP

这道题我不会，看了网上的题解才会的，涨了姿势，现阶段还是感觉区间DP比较难，主要是太弱。。。QAQ

思路中其实有贪心的意思，n个住户加一个商店，分布在一维直线上，应该是从商店开始，先向两边距离近的送，再往远的送。

这样肯定省时间，因为去了远的地方，近的地方自然就送了，不可能回来再送，所以我们可以开始定义状态

dp[i][j]代表送完从 i 到 j 所耗费的最小代价，但是我们发现此时状态虽然有了但是很难写出状态转移方程，

因为送完 i 到 j ，最后要么停在 i ,要么停在 j ,所以定义dp[i][j][0]代表停在 i ，dp[i][j][1]代表停在 j

记住一点，要把n+1个点（n个住户 加上一个商店）进行排序，从商店向两边由近及远进行dp

要更新dp[i][j][0]时，考虑最终是停在i，所以

dp[i][j][0]=min(dp[i+1][j][0]+t,dp[i][j][0]) t代表剩下的人等候的代价

dp[i][j][0]=min(dp[i+1][j][1]+t,dp[i][j][0])

要更新dp[i][j][1]时，考虑最终是停在j，所以

dp[i][j][1]=min(dp[i][j-1][0]+t,dp[i][j][0]) t代表剩下的人等候的代价

dp[i][j][1]=min(dp[i][j-1][1]+t,dp[i][j][0])

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstdlib>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

const int maxn=;

const LL INF=0x3f3f3f3f;

LL dp[maxn][maxn][],sum[maxn];

struct Node

{

    LL x,val;

    bool operator<(const Node &e)const

    {

        return x<e.x;

    }

} o[maxn];

int main()

{

    LL n,v,x;

    while(~scanf("%lld%lld%lld",&n,&v,&x))

    {

        for(int i=; i<=n; ++i)

            scanf("%lld%lld",&o[i].x,&o[i].val);

        ++n;

        o[n].val=,o[n].x=x;

        sort(o+,o++n);

        sum[]=;

        for(int i=; i<=n; ++i)

            sum[i]=sum[i-]+o[i].val;

        memset(dp,INF,sizeof(dp));

        int res;

        for(int i=;i<=n;++i)

        {

           if(o[i].x==x)

           {

               res=i;

               break;

           }

        }

        dp[res][res][]=dp[res][res][]=;

        for(int i=res;i>=;--i)

        {

            for(int j=res;j<=n;++j)

            {

                if(i==j)continue;

                dp[i][j][]=min(dp[i][j][],dp[i+][j][]+(sum[i]+sum[n]-sum[j])*(o[i+].x-o[i].x));

                dp[i][j][]=min(dp[i][j][],dp[i+][j][]+(sum[i]+sum[n]-sum[j])*(o[j].x-o[i].x));

                dp[i][j][]=min(dp[i][j][],dp[i][j-][]+(sum[n]-sum[j-]+sum[i-])*(o[j].x-o[j-].x));

                dp[i][j][]=min(dp[i][j][],dp[i][j-][]+(sum[n]-sum[j-]+sum[i-])*(o[j].x-o[i].x));

            }

        }

        printf("%lld\n",v*min(dp[][n][],dp[][n][]));

    }

    return ;

}