题目大意就是求一个矩阵中的最大子矩阵和。
求最大子矩阵和可以看作求最大子段和的二维平面版本，因此基本思路就是降维，将一行或一列进行压缩，然后再转化成求一维线段上的最大子段和。具体实现时可以用b[i,j]表示第j列从第1行到第i行的数字和，限定列压缩的起始行和结束行，用c[j]表示当前限制下到第j列为止的最大子矩阵和。记录下c[j]出现过的最大值即为最大子矩阵和。
7731901 IwfWcf 1050 Accepted 780K 47MS G++ 724B 2010-10-11 21:52:23
定义f[i,j]为生产前j个产品，最后一个在i机器上生产的最少耗费，容易推出朴素的状态转移方程。主要难点在于有同一台不能连续超过生产l个产品的规定，优化时间复杂度的关键在于降低在这l个状态中决策的时间复杂度。
定义g[i,j]为生产前j个产品，第j个在i机器上生产且第j-1个不在i机器上生产的最少耗费。易得f[i,j]=min(f[i,j],g[i,t]+sum[i,j]-sum[i,t])(j-l<t<=j);sum[i,j]表示在i机器生产前j个产品的费用和。可以发现影响决策的是g[i,t]-sum[i,t]的值，维护一个单调队列保存g[i,t]-sum[i,t](j-l<t<=j)的值，每次决策时取队首元素即可。
朴素的维护方法是利用堆来实现取最小的操作并在log(l)的时间内完成插入和删除操作。对于本题来说这一时间复杂度O(nnmlog(l))是可以接受的，但存在更优的方法使实际时间复杂度以及编程复杂度下降。显然当g[i,t]-sum[i,t]=g[i,p]-sum[i,p]时，若t>p，则保留p的状态就没有意义了。因此可以利用指针来维护一个单调队列，每次插入时二分寻找符合条件的插入点，并将队尾指针指向此。然后检查队首元素位置是否符合要求，如不符合则将队首指针后移，这样即可以实际时间复杂度远低于log(l)的代价完成队列的维护。对于本题的数据这一优化的效果非常明显。
R1216193 Accepted 100 From IwfWcf－ P1243 FPC Vivid Puppy 2009-4-21 2:26:30
非常经典的皇宫守护问题，用树形DP即可求解。对于每个点的覆盖可以分三种情况讨论：
分别用f[i,1],f[i,2],f[i,3]表示以上三种情况覆盖以该节点为根的子树所需的最少费用。则显然可以推出状态转移方程：
程序实现时用一个队列维护当前待处理的已经处理完全部叶节点的节点，最后加入队列中的节点就是根节点。
R1206607 Accepted 100 From IwfWcf－ P1144 FPC Vag 6K 2009-4-11 1:01:21
这题实际上就是要求一个图中的最大点集，要求点集中的每个点的度不小于k。不过据说数据太弱，只需要将初始度小于k的点剔除即可，不需要对删边进行处理。
还是简单说一下我的做法吧，先将初始度小于k的点剔除，并且将与其连接的点的度减1，在此过程中如果有某个点的度被剪到小于k则加入队列并标记已经处理过。然后对队列中的点做同样处理，一直到没有点可以加入队列，扫一次所有点的度，统计不小于k的点的个数输出即可。由于每个点最多入队一次，所以时间复杂度是O(n^2)。
R1191343 Accepted 100 From IwfWcf－ P1021 FPC Vivid Puppy 2009-3-28 21:37:25
挺有意思的一题，题目给出的信息实际上可以得到一些进一步的信息，显然如果a-b有偶数个1则1-(a-1)与1-b的1的个数的奇偶性相同，而如果a-b有奇数个1则1-(a-1)与1-b的1的个数的奇偶性必定不同。
用same[i]表示与i奇偶性相同的集合，用dif[i]表示与i奇偶性不同的集合，则对于a-b有偶数个1的信息，合并same[a-1]与same[b]的集合以及合并dif[a-1]与dif[b]的集合。若合并后same[a-1]=dif[b]或same[b]=dif[a-1]则可判定该信息不可能被满足。类似的，对于a-b有奇数个1的信息，合并same[a-1]与dif[b]的集合以及合并same[b]与dif[a-1]的集合，若合并后same[a-1]=same[b]则可判定该信息不可能被满足。但我们可以发现，经过集合合并，以上判定信息可以用same[a-1]=dif[a-1]或same[b]=dif[b]中的任意一条表示。
由于本题的区间范围很大但询问数很小，需要用离散化或hash来对区间的起点和终点进行处理。
R1188765 Accepted 100 From IwfWcf－ P1112 FPC Vivid Puppy 2009-3-27 0:27:09
二维树状数组，为了便于处理，将坐标全部做+1，sum[x1+1,y1+1,x2+1,y2+1]=sum[1,1,x2+1,y2+1]-sum[1,1,x1,y2+1]-sum[1,1,x2+1,y1]+sum[1,1,x1,y1];主要是注意做了转化后坐标处理的一些细节即可。
R1187587 Accepted 100 From IwfWcf－ P1512 FPC Vivid Puppy 2009-3-25 21:35:27
本题有一种很形象的解法，在[l,r]上种树可以表示为在l处添加一个左括号，在r处添加一个右括号。求[l,r]之间种的树的种类数即[1,r]中左括号的数量-[1,l-1]中右括号的数量。而求和操作可以利用树状数组在O(logn)的时间复杂度内完成，所以总的时间复杂度是O(mlogn)。
注意在种树时要维护的数组变量的元素的下标在计算中有可能会超过word的范围，要用longint。之前没发现这一点，以为是Vijos对writeln处理的bug导致最后两个点超时多交了几次。
R1185426 Accepted 100 From IwfWcf－ P1448 FPC Vivid Puppy 2009-3-23 23:50:35
博文
所有评论
