ZOJ 3469 Food Delivery（区间DP）

题意：
在一条直线上有一个餐厅和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 =  + ;

 int n, v, x;

 struct node

 {

     int x, b;

 }p[maxn];

 int sum[maxn];

 int d[maxn][maxn][];

 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 = ; i < n; i++)

             cin >> p[i].x >> p[i].b;

         //出发点

         p[n].x = x;

         p[n].b = ;

         sort(p, p + n +, cmp);

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

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

             d[i][j][] = d[i][j][] = INF;

         //前i个顾客的不满意度之和

         sum[] = p[].b;

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

         {

             sum[i] = sum[i - ] + p[i].b;

         }

         int k;

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

         {

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

             {

                 d[i][i][] = d[i][i][] = ;

                 k = i;

                 break;

             }

         }

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

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

         {

             if (i == j)  continue;

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

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

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

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

         }

         cout << min(d[][n][], d[][n][])*v << endl;

     }

 }