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

?

?