从AOJ的塔，到POJ的ferry loading，ferry loading到浙江省赛的第7题Process the Tasks，发现这三个问题都是一类比较典型的dp，有必要好好总结一下，避免以后再出现就不会了
这类题目比较原始的版本是
AOJ的塔问题(题目链接)
题意：给你一堆积木，选择其中的某些来组成两个相同高度的塔（对于某块积木，可以放在塔1，可以放在塔2，也可以都不放），问你最大组成的高度是多少？
解析：这个题目不太容易想，我是请教cxlove的（自己太水了），比较常规的想法是用两维表示塔1和塔2的高度，可是这样必然MLE，我们得选取另一个状态来进行DP，这个状态就是两个塔的高度差，dp【i】【j】表示前i个积木用于搭建了两座塔，相差高度为j的时候，两塔的最大高度和。
dp【i+1】【j+block【i+1】】=max（dp【i+1】【j+block【i+1】】，dp【i】【j】+block【i+1】）；这个表示i+1块积木放在较高的塔上
dp【i+1】【j-block【i+1】】=max（dp【i+1】【j-block【i+1】】，dp【i】【j】+block【i+1】）；这个表示i+1块积木放在较低的塔上
题目数据比较大，必须得用到滚动数组，而且还得继续优化，不然TLE，经过优化，可以达到300ms+。
详细代码见下方。
另一个差不多的题目是poj 2609 ferry loading（题目链接）
题意：给你两个相同车库，每个车库能装M长度的车子，现在给你一个车队（不能改变车队序列的顺序），每辆车子的长度，问你最多能装入多少辆汽车，输出路径
解析：这个题目和上一个题目差不多，不过这里还多了个限制，就是不能总长度超过M*2。
此题，个人能力有限。。没有弄出来输出路径，所以丑陋的代码就不贴了
还有一个题目，就是zoj 3331 浙江省赛的题目（题目链接）
题意：一个加工厂里面有两个机器人，然后有一堆货物需要加工，这些货物加工必须按照顺序来，第n件物品能进行加工的前提条件是n-1件物品加工完成或正在加工。
解析：这个题目相对上面两个题目复杂一点，但还是差不多，dp【i】【j】表示前i件物品加工完了（或i-1件正在加工中）的时候，j表示两个机器人的工作时间差距，dp表示最少耗费的时间。
其中j>0表示a机器人的工作时间更长，j<0表示b机器人工作时间更长
（更新）POJ 1015 （题目链接）
脑子转不过来，数据范围估算错误，不过学习了不少东西
题意：在n个数中选择K个数，使其和的绝对值最小。
解析：因为绝对值范围有限，所以直接开一维表示绝对值，其余的差不多。
状态转移方程比较麻烦，我直接在代码里面附上注释好了，详情见代码
/* aoj 518 塔*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INF 1<<29
int dp[2][500010];
int a[51],sum[51];
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int main()
{
int n,i,j;
int t;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
qsort(&a[1],n,sizeof(a[0]),cmp);
sum[1]=a[1];
for(i=2;i<=n;i++)
sum[i]=sum[i-1]+a[i];//提前算出高度差，然后枚举高度差的时候就不用编立500000了
for(i=0;i<=sum[n];i++)
dp[0][i]=-INF;
dp[0][0]=0;
for(i=0;i<n;i++)
{
t=(i+1)&1;
for(j=0;j<=sum[n];j++)
dp[t][j]=-INF;
for(j=0;j<=sum[i];j++)
{
if(dp[t][j+a[i+1]]<dp[i&1][j]+a[i+1])//放在较高的塔
dp[t][j+a[i+1]]=dp[i&1][j]+a[i+1];
if(dp[t][abs(j-a[i+1])]<dp[i&1][j]+a[i+1])//放在较低的塔
dp[t][abs(j-a[i+1])]=dp[i&1][j]+a[i+1];
if(dp[t][j]<dp[i&1][j])
dp[t][j]=dp[i&1][j];
}
// printf("I:%d 0:%d 1:%d 2:%d 3:%d\n",i+1,dp[(i+1)&1][0],dp[(i+1)&1][1],dp[(i+1)&1][2],dp[(i+1)&1][3]);
}
if(dp[n&1][0]/2<=0) printf("-1\n");
else printf("%d\n",dp[n&1][0]/2);
}
return 0;
}
/*zoj 3331 */
#include<iostream>
#include<string.h>
#define offset 100
#define INF 1<<25
#define min(a,b) ((a)<(b)?(a):(b))
#define get(a) ((a)<0?0:(a))
using namespace std;
const int maxn=105;
int dp[maxn][maxn*2];
int costa[maxn],costb[maxn];
int n,m;
int main()
{
int i,j,k,T;
cin>>T;
while(T--)
{
cin>>n;
for(i=1;i<=n;i++)
cin>>costa[i]>>costb[i];
for(i=0;i<=n;i++)
for(j=0;j<210;j++)
dp[i][j]=INF;
dp[0][0+offset]=0;
for(i=0;i<n;i++)
for(j=-100;j<=100;j++)
{
if(dp[i][j+offset]!=INF)
{
if(j<=0)//b在上面(机器人b的工作时间比较长）
{
dp[i+1][-costb[i+1]+offset]=min(dp[i+1][-costb[i+1]+offset],dp[i][j+offset]+costb[i+1]);//放在B上面（继续由机器人b加工
dp[i+1][costa[i+1]+j+offset]=min(dp[i+1][costa[i+1]+j+offset],dp[i][j+offset]+get(j+costa[i+1]));//放在a上面，由机器人A加工
// printf("I:%d J:%d dP:%d\n",i,j,dp[i][j+offset]);
}
else//a在上面（机器人a的工作时间比较长）
{
dp[i+1][costa[i+1]+offset]=min(dp[i+1][costa[i+1]+offset],dp[i][j+offset]+costa[i+1]);//放在A上面，继续让机器人A加工
dp[i+1][j-costb[i+1]+offset]=min(dp[i+1][j-costb[i+1]+offset],dp[i][j+offset]+get(costb[i+1]-j));//放在b上面，继续由机器人B加工
// printf("I:%d J:%d dP:%d\n",i,j,dp[i][j+offset]);
}
}
}
int ans=INF;
for(j=-100;j<=100;j++)
if(dp[n][j+offset]<ans)
ans=dp[n][j+offset];
cout<<ans<<endl;
}
return 0;
}