以下所有题来自
www.vijos.org
太水的DP题就略过了。
Vijos_1002 过河
数轴上的区间[0,L],其中有M个点上有石子,青蛙从0点出发，要跳到L点或者大于L点，青蛙具有一个跳跃区间[s,t],1<=s<=t,从x点跳只能跳到[x+s,x+t]这段区间.问青蛙
最少踩到的石头树.
（L<=10^9,M<100）
题解：
首先可以想到的转移是f[i]=MIN{f[i-j]+(if 有石子),s<=j<=t},时间复杂度O(L*10),超时.注意到M只有100，也就是说，区间上的石头是非常稀疏的，因此，我们对石头距离
超过100的，距离变成100，（因为s,t<=10, 100以后能跳到的地方，改成100依
然能跳到）。O(M*100*10)，AC。
Vijos_1014
现在笛卡尔平面上有n(n<=1000)个点，每个点的坐标为(x,y)(-2^31<x,y<2^31，且为整数)，任意两点之间相互到达的代价为这两点的欧几里德距离，现要你编程求
出最短bitonic tour。
注释：bitonic tour:要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达，并且环游的路线只能是从最西端单向到最东端，再
单项返回最西端，并且是一个哈密尔顿回路.
题解：
我们换个角度去考虑。两个人从源点出发（最西段）要到达终点（最东），且每个人经过的点不能跟另一个人相同，两个人的路径并起来就是一个环，且覆盖所有
点。先把所有点排序（key1为x，key2为y)，f[i][j]表示第一个人走到第i个点，第二个人走到j点，我们可以强制i>j（对称性，因此f[i][j]=f[j][i]) ，如果i>j+1的时候，
那么i-1这个点必然是第一个人走的（j还没达到i-1），f[i][j]=f[i-1][j]+dis(i-1,i) i>j+1，如果i=j+1的时候，则f[i][j]=MIN{f[k][j]+dis(k,i)} (1<=k<j) ，但因为k<j，而我们
强制的选择i>j，因此f[k][j]的值是未求出的，因此把f[k][j]换成f[j][k]，这样转移就全部得到了。
f[i][j]=MIN{f[k][j]+dis(k,i),1<=k<j} i=j+1
f[i-1][j]+dis(i-1,i) i>j+1
时间复杂度O(N^2)
Vijos_1037
有N块积木，每块积木都有一个高度Wi，现在要从这N块积木中选取一些来搭建两座塔，要求两座塔的高度相同，求最大高度。
N<=100,Sigma(Wi)<=2000.
题解：
易得到这样的一个转移，i表示取到第i块积木，第一座塔高度为h1,第二座塔高度为h2,f[i][h1][h2]表示取到第i块积木的时候，高度分别为h1,h2的双塔能否得到
f[i][h1][h2]=f[i-1][h1][h2] or f[i-1][h1-wi][h2] or f[i-1][h1][h2-wi]，时间复杂度O(N*Sigma(Wi)^2),超时。
优化：其实h1,h2里真正有用的信息是他们的差(H1-h2),用f[i][x]表示取到第i块积木的时候高度差为x的最大高度。答案即为f[n][0]。
转移的时候有4种情况。
1.第i块积木不要。f[i][x]=f[i-1][x]
2.第i块积木加在高度高的塔上f[i][x]=f[i-1][x-wi] +wi (x>=wi)
3.第i块积木加在高度低的塔上，且加了之后，高度依然低于高度高的塔。f[i][x]=f[i-1][x+wi]
4.第i块积木加在高度低的塔上，且加了之后，高度高于之前高度高的塔。f[i][x]=f[i-1][wi-x]+x;
Vijos_1057
给定一个N*M的矩阵，矩阵内只有两种数字，0,1，求最大的正方形边长，要求正方形内的数字全部为1.
题解：
很经典的DP。f[i][j]表示以i，j为正方形右下角的最大边长。
f[i][j]=MIN{f[i-1][j],f[i][j-1][,f[i-1][j-1]}+1 (i,j)上的数字为1
f[i][j]=0 (i,j)上的数字为0
这个MIN可能不好理解。是这样的:如果f[i][j]的边长为X，那么f[i-1][j-1]，f[i][j-1]，f[i-1][j]的边长至少为X-1。（必须要全部满足，因此是MIN，而不是MAX）
Vijos_1243
生产产品需要M个步骤，总共有N台机器，cost[i][j]表示第i台机器完成第j个步骤需要的时间，每个机器最多只能连续完成L个步骤，产品从一个机器移到另一个机器需要额外的时间extra，问完成M个步骤的最少耗时。(n<=6,m<=100000,L<=50000)
题解：
容易得到这样的转移。f[i][k]表示做到第i步时，产品在第k台机器上。
f[i][k]=MAX(f[j][p]+sum[k][i]-sum[k][j]， i-j<=L) 时间复杂度O(N^2*M*L) 超时
单调队列优化即可。时间复杂度O(N^2*M)
Vijos_1412
求0/1背包的前k优解。
题解：
用f[w]数组记录重量为w时的前k优解。则每次更新可以理解成两个有序序列的merge操作。时间复杂度O(N*M*K)
Vijos_1642
给出一颗有N个结点的带权多叉树，并且有一个约束条件（要想选取u，他的父亲必须被选取）。求选取m个点，使权值和最大。
(n,m<=1000)
题解：
很经典的树形依赖背包，O(NM)的解法详见徐持衡的NOI2009论文《浅谈几类背包问题》