Food Delivery

题目链接：https://vjudge.net/problem/ZOJ-3469#author=SCUACM2020

题意：你要给n个顾客送外卖，第i个顾客在a[i].x位置，且每过1min第i个顾客就会增加a[i].v的怒气。你的初始位置在p点，且你走1米所用的时间是m分钟。问你送完所有的外卖，顾客的怒气值之和最小是多少。

思路：区间dp，出发先往左右中间靠近的送，再往两边送省时间。设dp[i][j][0]表示从i到j用户送到最小不开心值，此时送货员停留在左边即i位置，dp[i][j][1]表示从i到j用户送到最小不开心值，此时送货员停留在右边即j位置。

状态转移：

            dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1].x-a[i].x)*(s+a[i].v));
            dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j].x-a[i].x)*(s+a[i].v));
            dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j].x-a[i].x)*(s+a[j].v));
            dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j].x-a[j-1].x)*(s+a[j].v));

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x7ffffff
const int maxn = 1005;
const int mod = 1000000007;
int dp[maxn][maxn][2];
int sum[maxn];
int n,m,p;
struct node
{
    int x,v;
} a[maxn];
bool cmp(node x,node y)
{
    return x.x<y.x;
}
void DP()
{
    int res;
    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++)
    {
        if(a[i].x==p)
        {
            res=i;
            break;
        }
    }
    dp[res][res][0]=dp[res][res][1]=0;
    for(int i=res; i>=1; i--)
    {
        for(int j=res; j<=n; j++)
        {
            int s=sum[i-1]+sum[n]-sum[j];
            if(i==j)
                continue;
            dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1].x-a[i].x)*(s+a[i].v));
            dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j].x-a[i].x)*(s+a[i].v));
            dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j].x-a[i].x)*(s+a[j].v));
            dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j].x-a[j-1].x)*(s+a[j].v));
        }
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&p))
    {
        for(int i=1; i<=n; i++)
            cin>>a[i].x>>a[i].v;
        n++;
        a[n].x=p;
        a[n].v=0;
        sort(a+1,a+n+1,cmp);
        for(int i=1; i<=n; i++)
            sum[i]=sum[i-1]+a[i].v;
        DP();
        cout<<min(dp[1][n][0],dp[1][n][1])*m<<endl;
    }
}