DP还是搜索？DP的最高境界---zoj_3469

       http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3469       

      终于然我摸到了一点点DP的最高境界。。。 

      题目大意：餐馆送外卖，分布在一条直线上，给出N,V,X表示订单数，速度的倒数，餐馆的位置，然后给出叫外卖的位置Xi和Bi，Bi表示等待外卖的人的不满意指数的增长率（每分钟），求一条送外卖的路径，使得所有外卖送到后，所有人的不满意指数之和的最小。

       很显然，送货员的路径肯定是左右来回的，DP[i][j][k]表示从位置i到j全部送到并且送货员在最左边k=0或者最右边k=1的代价。那么DP[i][j][0]的子结构很显然是DP[i-1][j][0]和DP[i-1][j][1]，DP[i][j][1]的子结构是DP[i][j-1][0]和DP[i][j-1][1]

       这里的代价的表示有点高端，如果直接表示不满意指数，那么没有存时间我们发现无法计算状态转移后的值。因此，DP[i][j][k]存的是位置i到j的代价以及i之前和j之后的累加代价。当DP[i][j][k]更新之后，i到j之间的代价已经不需要更新了，因为已经送到了。

       有了DP的思路，但是我们发现，实现的过程要递归，因为当我们更新完DP[l][r][k]的时候（l,r为左右端点），除了DP[l][r][k]，其他的值并不是我们的结果，因为还包括了左右端点以外的代价，而DP[l][r][k]左右端点以外的代价已经是0.

       具体的实现细节见代码（watashi）：

zoj_3469:

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const int inf = 1000000000;

int dp[1001][1001][2];
int nl, nr;
vector<pair<int, int> > vl, vr;

int gao(int l, int r, int p) {
	int &ret = dp[l][r][p];

	if (ret == -1) {
		ret = inf;
		if (p == 0) {
			if (l != 0) {
				int tmp = vl[l - 1].second + vr[r].second;
				ret = min(ret, gao(l - 1, r, 0) + (vl[l].first - vl[l - 1].first) * tmp);
				ret = min(ret, gao(l - 1, r, 1) + (vl[l].first + vr[r].first) * tmp);
			}
		} else {
			if (r != 0) {
				int tmp = vl[l].second + vr[r - 1].second;
				ret = min(ret, gao(l, r - 1, 0) + (vl[l].first + vr[r].first) * tmp);
				ret = min(ret, gao(l, r - 1, 1) + (vr[r].first - vr[r - 1].first) * tmp);
			}
		}
	}

	return ret;
}

int main(void)
{
	int n, v, x, xx, bb;
	freopen("e:\\zoj\\zoj_3469.txt","r",stdin);
	while (scanf("%d%d%d", &n, &v, &x) != EOF) {
		vl.clear();
		vr.clear();
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &xx, &bb);
			if (xx > x) {
				vr.push_back(make_pair(xx - x, bb));
			}
			else if (xx < x) {
				vl.push_back(make_pair(x - xx, bb));
			}
		}

		vl.push_back(make_pair(0, 0));
		vr.push_back(make_pair(0, 0));
		sort(vl.begin(), vl.end());
		sort(vr.begin(), vr.end());
		nl = vl.size() - 1;
		nr = vr.size() - 1;
		for (int i = 0; i < nl; i++) {
			vl[i].second = vl[i + 1].second;
		}
		vl[nl].second = 0;
		for (int i = nl; i > 0; i--) {
			vl[i - 1].second += vl[i].second;
		}
		for (int i = 0; i < nr; i++) {
			vr[i].second = vr[i + 1].second;
		}
		vr[nr].second = 0;
		for (int i = nr; i > 0; i--) {
			vr[i - 1].second += vr[i].second;
		}

		for (int i = 0; i <= nl; i++) {
			for (int j = 0; j <= nr; j++) {
				dp[i][j][0] = dp[i][j][1] = -1;
			}
		}
		dp[0][0][0] = 0;
		dp[0][0][1] = 0;
		printf("%d\n", v * min(gao(nl, nr, 0), gao(nl, nr, 1)));
	}

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//719 	2011-02-11 12:32:00 	Accepted 	C 	C++ 	400 	8008 	watashi@ArcOfDream 	Source