Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1476
一道想了很久做了很久很久的DP题。
真真正正地算是自己做出来了，没有参考任何东西。
开始的时候是要像以前的Cash Machine之类的题那样记录所有的情况，但是后来发现可能会有重复的现象。
之后打算开个二维数组记录，谁知道老是报RTE。
直到今天，终于想出来了。
思路：开一个一维数组，记录“差”的情况，同时记录最大值。所谓的“差”，就是两堆礼物的高度差。而最大值是指在这个差下能达到的最大高度。
比如第一个数据：4 1 3 10。
开始把0设为已访问，高度为-1。
读入4，则差的情况增加了一个，即是4。同时在差为4的情况下的相同高度值为0。
之后读入1，差的情况增加了三个，有1（从0产生）、3、5（3和5均从4产生）。1的高度为0，而3的高度为1，5的高度为0。因为当两堆一堆为0一堆为4时，增加1则可以变成（1、4）或（0、5），第一种情况差为3，高度为1；第二种情况差为5，高度为0。
如此类推，到最后0的高度即是所求答案。
为了避免对每一份礼物增加后对后面的判断产生干扰，需要新开一个数组记录本次新增加的值。同时在本次循环结束后把该数组里的值增加到原数组里，并清空该数组（这里我用了vector）。
以下贴代码：
#include <iostream>#include <vector>using namespace std;int maxh[5005],num[105];bool visited[5005];struct gift{ int dif; int max;};int getmax(int a, int b){ if (a>=b) return a; else return b;}int main(){ vector<gift>v; gift g; int n,i,j,mid,right; while(scanf("%d", &n)!=EOF) { mid = 0; for (i=1; i<=n; i++) { scanf("%d", &num[i]); mid += num[i]; } mid /= 2; right = 0; for (i=0; i<=mid; i++) { maxh[i] = 0; visited[i] = false; } visited[0] = true; maxh[0] = -1; for (i=1; i<=n; i++) { v.clear(); for (j=0; j<=right; j++) { if (visited[j]==true) { if (j+num[i]<=mid) { g.dif = j+num[i]; g.max = maxh[j]; v.push_back(g); } if (j-num[i]>=0) { g.dif = j-num[i]; g.max = maxh[j] + num[i]; v.push_back(g); } } } for (j=0; j<v.size(); j++) { visited[v[j].dif] = true; maxh[v[j].dif] = getmax(v[j].max,maxh[v[j].dif]); right = getmax(right, v[j].dif); } } printf("%d/n", maxh[0]); } return 0;}
p.s.我说怎么做这道题这么累捏= =
