UVa 1628 Pizza Delivery
题目：
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51189
思路：
本体与修缮长城一题有所相似。所以解法有相似之处。
不同之处就是本体可能会产生负情况，即送餐时间晚了客户会反过来找你要钱所以需要放弃，但修缮长城只有费用，顺手修了肯定是一个不错的选择。
依旧将区间两端与位置作为状态不过要添加一维cnt表示还需要送餐的人数。类似地定义：d[i][j][cnt][p]表示已经送完了ij区间（区间内或送餐或放弃）位于p（p==0||p==1）还剩下cnt个客户需要继续送餐。添加的一维成功解决了不知道还有多少的客户需要送餐的问题。这里注意到DP过程中利用的信息都来源于状态，因此定义的状态必须要提供转移足够的信息，这样才能得到所需要的值。
转移方程：
d[i][j][cnt][p]=max{d[i][k][cnt-1][1]+pay[knew]//k在余下的右区间 , d[k][j][cnt-1][0] +pay[knew]//k在余下的左区间}
代码：
1 // UVa1628 Pizza Delivery 2 // Rujia Liu 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 8 const int maxn = 100 + 5; 9 10 int kase, n; 11 int p[maxn], v[maxn]; 12 int d[maxn][maxn][maxn][2]; 13 int vis[maxn][maxn][maxn][2]; 14 15 // already considered s~e, still need to delivery to cnt people. 16 // pos = 0 means at s, pos = 1 means at e 17 int dp(int s, int e, int cnt, int pos) { 18 if(cnt == 0) return 0; //cnt==0 return 19 20 int &ans = d[s][e][cnt][pos]; //记忆化搜索 21 if(vis[s][e][cnt][pos] == kase) return ans; 22 vis[s][e][cnt][pos] = kase; 23 24 ans = 0; 25 //枚举的i与之前区间相间的部分默认为不会送餐 //比较得出max_ans 26 if(!pos) { //pos==s 27 for(int i = 0; i < s; i++) //s->i //i在区间的左边 28 ans = max(ans, v[i] - cnt * abs(p[i] - p[s]) + dp(i, e, cnt - 1, 0)); 29 //ans=max(ans,足够已知的未来价值+子问题价值) 30 for(int i = e + 1; i < n; i++) //s->i //i在区间的右边 31 ans = max(ans, v[i] - cnt * abs(p[i] - p[s]) + dp(s, i, cnt - 1, 1)); 32 } 33 else { //pos==e 34 for(int i = 0; i < s; i++) //e->i //i在区间的左边 35 ans = max(ans, v[i] - cnt * abs(p[i] - p[e]) + dp(i, e, cnt - 1, 0)); 36 for(int i = e + 1; i < n; i++) //e->i //i在区间的右边 37 ans = max(ans, v[i] - cnt * abs(p[i] - p[e]) + dp(s, i, cnt - 1, 1)); 38 } 39 return ans; 40 } 41 42 //DP要枚举出所有具有最优可能性的情况 不能遗漏否则问题就可能不是最优 43 44 int main() { 45 int T; 46 scanf("%d",&T); 47 memset(vis, 0, sizeof(vis)); 48 for(kase = 1; kase <= T; kase++) { 49 scanf("%d", &n); 50 for(int i = 0; i < n; i++) scanf("%d", &p[i]); //位置[] 51 for(int i = 0; i < n; i++) scanf("%d", &v[i]); //原利[] 52 53 int ans = 0; 54 for(int k = 1; k <= n; k++) //枚举送餐人数 55 for(int i = 0; i < n; i++) //枚举给送餐的第一个人 56 ans = max(ans, v[i] - k * abs(p[i]) + dp(i, i, k - 1, 0)); //枚举比较 make_max 57 printf("%d ",ans); 58 } 59 return 0; 60 }