ZOJ 3469 Food Delivery（区间DP）

https://vjudge.net/problem/ZOJ-3469

题意：
在一条直线上有一个餐厅和n个订餐的人，每个人都有随时间上升的不满意值，从餐厅出发，计算出送完时最小的不满意值总和。

思路：
这道题和UVa 1632这道题目很像，只不过1632可以从任一点出发，而这题必须从餐厅出发。1632每个坐标几秒之后就会消失，这题是每分钟不满意值会上升，比较类似，都是挺不错的区间DP题。

d[i][j][0]代表的是在送完i~j这个区间的最小不满意值，并且此时人处于左端，d[i][j][1]则是人处于右端。

状态转移的话看代码吧，d[i][j][]的话可以从d[i+1][j][]过来，也可以从d[i][j-1][]过来。

#include<iostream> 
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define INF 0x3f3f3f3f  
const int maxn = 1000 + 5;

int n, v, x;

struct node
{
    int x, b;
}p[maxn];

int sum[maxn];
int d[maxn][maxn][2];

bool cmp(node a, node b)
{
    return a.x < b.x;
}

int main()
{
    //freopen("D:\txt.txt", "r", stdin);
    while (cin >> n >> v >> x)
    {
        for (int i = 0; i < n; i++)
            cin >> p[i].x >> p[i].b;

        //出发点
        p[n].x = x;
        p[n].b = 0;
        sort(p, p + n +1, cmp);

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

        //前i个顾客的不满意度之和
        sum[0] = p[0].b;
        for (int i = 1; i <= n; i++)
        {
            sum[i] = sum[i - 1] + p[i].b;
        }

        int k;
        for (int i = 0; i <= n; i++)
        {
            if (p[i].x == x)
            {
                d[i][i][0] = d[i][i][1] = 0;
                k = i;
                break;
            }
        }

        for (int i = k; i >= 0;i--)
        for (int j = k; j <= n; j++)
        {
            if (i == j)  continue;
            d[i][j][0] = min(d[i][j][0], d[i + 1][j][0] + (p[i + 1].x - p[i].x)*(sum[n] + sum[i] - sum[j]));
            d[i][j][0] = min(d[i][j][0], d[i + 1][j][1] + (p[j].x - p[i].x)*(sum[n] + sum[i] - sum[j]));
            d[i][j][1] = min(d[i][j][1], d[i][j - 1][1] + (p[j].x - p[j - 1].x)*(sum[n] - sum[j - 1] + sum[i - 1]));
            d[i][j][1] = min(d[i][j][1], d[i][j - 1][0] + (p[j].x - p[i].x)*(sum[n] - sum[j - 1] + sum[i - 1]));
        }
        cout << min(d[0][n][0], d[0][n][1])*v << endl;
    }
}