C++博客-wolf5x@bupt

new blog url...

Wed, 18 Sep 2013 06:48:00 GMT

wolf5x 2013-09-18 14:48 发表评论

The "Clockwise/Spiral Rule"

Wed, 31 Aug 2011 05:07:00 GMT

void (*signal(int, void (*fp)(int)))(int);
Question:
What is 'signal' ?

#include <cstdio>
using namespace std;

void f(int);
void (*pf)(int), (*qf)(int);
void (*hf(int, void(*)(int)))(int);

typedef void (*sighandler_t)(int);

sighandler_t signal(int, sighandler_t);


void f(int a) 
{
    printf("void f(int %d)\n", a);
}

void (*hf(int _i, void(*_pf)(int)))(int)
{
    printf("_i = %d\n", _i);
    _pf(_i);
    return _pf;
}

sighandler_t signal(int signum, sighandler_t sighandler)
{
    printf("signal num = %d\n", signum);
    sighandler(signum);
    return sighandler;
}

int main()
{
    pf = &f;
    qf = hf(12, pf);
    qf(23);
    
    signal(54, f);
    return 0;
}

void (*signal(int, void (*)(int)))(int);
Answer:
signal is a function, passing {an int and a pointer [to a function passing an int returning nothing (void)]}, returning {a pointer [to a function passing an int returning nothing (void)]}.

wolf5x 2011-08-31 13:07 发表评论

pku 3697 USTC campus network O(M)

Sun, 14 Aug 2011 19:06:00 GMT

08合肥网赛某题。
http://poj.org/problem?id=3697
题意是问在N个点的完全图(N<=10,000)中删掉M(M<=1,000,000)条边后, 还有多少个点与顶点1连通(顶点编号从1开始).
暴力BFS+HASH+各种WS优化的方法很多, 但是出题人原意应该是O(M)的做法吧... 下面是我YY出来的O(M)的做法.

只考虑这M条待删边, 能得到什么信息呢? 可以先从点1入手. 扫一遍与1邻接的点, 那么剩下没被扫到的点肯定与1是连通的. 而被扫到的点是"有可能"与1不连通. 所以就把那些肯定与1连通的点做标记. 从这些确定连通的点中任选一个u, 再扫描它的所有邻接点. 这之后, 如果一个点一共被扫了2次, 那么它才"有可能"与1不连通, 其它少于2次的点肯定与1连通, 因为它或者与1连通, 或者与u连通, 而u是已知与1连通的. 这样再拿出一个已经确定连通的点, 扫描它的邻接点, 把被扫过次数<3的又标记为已连通......

经过上面的YY, 算法基本上就出来了:
把已知肯定与1连通的点集称为S, 剩下不确定的为T. 一开始, S中只有1这一个点, 其它点都在T中. 每个点有个计数器, 记录自己被扫了多少次.
1) 从S中取出一个没处理过的点, 把它标记为已处理, 并遍历它的所有邻接点, 被遍历到的点的计数器都+1.
2) T中所有"计数3) 重复1), 直到S中所有点都处理完.
这时, S中的点就是与1连通的, T中剩下的就是不连通的.

复杂度分析:
读入边和扫描边都是O(M)的.
S集可以用队列维护, 总共O(N).
T集的维护: 每一轮都要扫一遍当前的T, 把所有计数小的删掉, 放进S中. 这样, 这一步的总复杂度就是O(sigma(T)), 会不会到达O(N^2)呢? 实际上是不会的. 因为一条边最多只会使一个顶点的计数+1, 因此每一轮还剩在T中的点数不会超过这一轮遍历过的边数. 这样, 所有回合的sigma(T)就肯定不会超过总边数. 因此这里总共也是O(M)的. 严格来说算上第1轮有N-1个点, 也是O(M+N).
这样总的复杂度就是O(M)了.

不过这个算法读入用scanf时, g++跑了1000+ms, 改成getchar才到200+ms的. 不知道排前面的神们是不是有更NB的算法.

代码:

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 using namespace std;
 7 
 8 const int MAXN = 10010;
 9 const int MAXM = 1000010;
10 
11 struct Edge {
12     int v, next;
13 }edg[MAXM*2];
14 int ecnt, gg[MAXN];
15 bool yes[MAXN];
16 int que[MAXN], pq, sq, cnt[MAXN], vt[MAXN], nt;
17 int N, M;
18 
19 inline int getnextint()
20 {
21     int r = 0;
22     char c;
23     while(!isdigit(c=getchar())); 
24     do{
25         r = r*10 + c-'0';
26     } while(isdigit(c=getchar()));
27     return r;
28 }
29 
30 inline void addedge(int u , int v)
31 {
32     edg[ecnt].v = v; edg[ecnt].next = gg[u], gg[u] = ecnt++;
33     edg[ecnt].v = u; edg[ecnt].next = gg[v], gg[v] = ecnt++;
34 }
35 
36 int main()
37 {
38     int cas = 0;
39     while(~scanf("%d%d", &N, &M) && !(N==0 && M==0)){
40         
41         ecnt = 0;
42         for(int i = 0; i < N; i++){
43             gg[i] = -1;
44             yes[i] = i==0 ? true : false;
45             cnt[i] = 0;
46             vt[i] = i+1;
47         }
48         nt = N-1;
49         
50         for(int i = 0; i < M; i++){
51             int u = getnextint();
52             int v = getnextint();
53             addedge(--u, --v);
54         }
55         
56         pq = sq = 0;
57         que[sq++] = 0;
58         yes[0] = true;
59         
60         while(pq != sq) {
61             int u = que[pq++];
62             for(int e = gg[u]; e >= 0; e = edg[e].next) {
63                 if(!yes[edg[e].v])
64                     cnt[edg[e].v]++;
65             }
66             for(int i = 0; i < nt; i++) {
67                 while(i < nt && cnt[vt[i]] < pq) {
68                     yes[vt[i]] = true;
69                     que[sq++] = vt[i];
70                     if(i < --nt) 
71                         vt[i] = vt[nt];
72                 }
73             }
74         }
75         printf("Case %d: %d\n", ++cas, sq-1);
76         
77     }
78     return 0;
79 }

wolf5x 2011-08-15 03:06 发表评论

srm 514 div1 250 600 900

Wed, 10 Aug 2011 06:30:00 GMT

250pt MagicalGirlLevelOneDivOne
某神在(0,0)处, 需要走到(x,y)处(0
很明显, 此神可以沿任意方向2步2步的走, 即先走个(+1,-n), 再走个(+1,+n). 所以能否到终点, 只与奇偶性有关.
经过一阵分类讨论可知:
1) 如果x+y=0(mod 2), 则YES.
2) 如果x+y=1(mod 2), 且n[i]中有偶数, 则YES.
3) 否则NO.

[杂]

600pt MagicalGirlLevelTwoDivOne
给一个H*W(1<=H,W<=50)的矩阵A, 每一位上已经有一个1~9的数字, 或者是个'.', 在'.'处可以填上任意1~9的数字. 再给出n和m(1<=n<=min{10,H}, 1<=m<=min{10,W}). 问一共有多少种填'?'的方法, 使得整个矩阵满足:
对任意的r和c, 以(r,c)开始的水平方向上连续m个数之和是奇数;
对任意的r和c, 以(r,c)开始的垂直方向上连续n个数之和是奇数.

首先要注意到一个性质: 对任意r和c有 A[r,c]与A[r+n,c]的奇偶性相同. 很显然, 因为要满足A[r,c]+A[r+1,c]+...+A[r+n-1,c]与A[r+1,c]+...+A[r+n-1,c]+A[r+n,c]的奇偶性相同, 都是奇数. 列上同样有A[r,c]与A[r,c+m]奇偶性相同.
因此在一行上, 只用记录n位的奇偶状态, 列上同理. 这样,所有的(r+pn,c+qm)都能合并成同一个点, 且只有两种状态: 奇和偶. 合并后该点为奇(或偶)的方法数, 等于组成它的所有点方法数之积. 最后整个矩阵合并压缩成一个n*m的矩阵, 就可以用状态DP来搞, 求每行每列之和都为奇的方法数. dp[n][1<
觉得是道很好的题, 状态设计很巧妙...

[状态DP 状态压缩设计]

900pt MagicalGirlLevelThreeDivOne
某神给出K(K<=50)个01串, 每个串的长度不超过50. 用这些串组成新的串放到数组A[]里. 如果i=0的最大整数. 现在此神给出n, lo, hi, 要你求A[n]的子串A[n][lo...hi]中有多少个连续的1. 0<=n<=10^15, 0<=hi<= min{A[n]的长度, 10^15}, 0<=lo<=hi. 所有计数以0开始.

首先随便打个表或者手推一下化简A[i]的递推式, 可以发现当i>=2*K时, A[i] = A[i-1] + (A[i-K-1] + ... A[i-p*K-1]) = A[i-1] + A[i-K], 而K<=50. 所以A[i]的长度关于i是指数增长的, 50log(10^15)可能够用(严格证明不太会, 求指导#.#). 因此其实n<=10^15范围是坑爹的, hi不会超过A[10^4]的长度. 而这些串的前缀都是一样的, 所以A[n][lo..hi]其实与A[10^4][lo..hi]相同.
这样便可直接利用A[i] = A[i-1] + A[i-K]的关系分治. 和用线段树求最长连续1串的思想差不多: 每个结点的状态变量是(id,lo,hi), 存放A[id][lo..hi]的最优解. 除了存放当前段的最大长度max外, 为了能合并子区间, 还要记录当前区间从左端开始连续1的个数sl, 和从右端开始连续1的个数sr. 剩下的工作与线段树无异, 假设要求(id, lo, hi)的(max, sl, sr):
对于A[id], 它的左儿子就是A[id-1], 右儿子是A[id-K].
1)如果id<2*K, 直接暴力.
2)如果lo>=len[id-1](类似于线段树中的查询区间完全落在右儿子), 则递归查询(id-K, lo-len[id-1], hi-len[id-1]).
3)如果hi4)否则两个儿子都要查询, 并根据返回的结果求当前区间的结果.

分治思想很强大, 用map写的"线段树"很YD, 偶依然蒻爆了.

[分治复杂度分析]

wolf5x 2011-08-10 14:30 发表评论

srm 513 div1 500 1000

Sat, 30 Jul 2011 03:04:00 GMT

500pt Perfect Memory
题意: 某神在M*N(1<=M, N<=50, M*N为偶数)的格子上玩对对碰: 每个格子都有个隐藏的图形. 此神一次行动翻开2个, 如果相同, 就成功消去这2个格子. 如果不相同, 那这2个格子又恢复隐藏状态. 但是此神记忆力很NB, 能记住所有翻开过的格子是什么图形. 还有重要的一点, 他一次行动时, 是先翻开1个格子, 知道它的图形之后, 再决定怎么翻第2个格子, 而不是两个格子同时翻开. 问此神把所有格子都消去, 需要消耗的行动次数的期望.

容易想到期望与翻格子的位置无关. 有关的量是: 当前还有多少对图形没被消去. 其中有多少对图形已经知道其中一个的位置了. so, dp[i][j], i为前者, j为后者. 一次行动中, 第1个格子肯定翻之前没翻过的(一共有2i-j个, 记为s), 除非已经知道某1对的位置, 直接把2个都翻出来消掉. 所以转移有几种情况:
1) 从s中翻出1个新图形. 从剩下s-1中翻出了相同图形, 消除. 这样的概率是2(i-j)/s * 1/(s-1), 转移到dp[i-1][j].
2) 从s中翻出1个新图形. 从剩下s-1中又翻出新图形, 这样就多了2种已知图形. 概率是2(i-j)/s * 2(i-j-1)/(s-1), 转移到dp[i][j+2].
3) 从s中翻出1个新图形. 从剩下s-1中翻出了之前j个已知图形中的一个. 这样, 下一次就可以消耗一次行动把那对已知图形消去, 转移到dp[i-1][j], 概率是2(i-j)/s * j/(s-1).
4) 从s中翻出1个已知图形. 直接翻出与它配对的消去. 转移到dp[i-1][j-1], 概率是j/s * 1.

所以 dp[i][j] = p1*(dp[i-1][j]+1) + p2*(dp[i][j+2]+1) + p3*(dp[i-1][j]+2) + p4*(dp[i-1][j-1]+1).
其中2)的条件是i>=j+2, 4)的条件j>=1. 边界dp[i][i] = i. 最后dp[M*N][0]即为所求.

[概率期望 DP]

1000pt Reflections
题意: 某神在三维空间中玩一个游戏, 空间中有N个(N<=20)平面, 每个平面都垂直于某个坐标轴, 并且与该坐标轴交于整点. 此神从(0,0,0)处出发, 想去(X,Y,Z)处. 现在他每行动一次可以做如下移动:
1) 走到与他相邻的1个整点上, 即(x+1, y, z) (x-1, y, z) (x, y+1, z) (x, y-1, z) (x, y, z+1) (x, y, z-1)中的一个.
2) 神一次行动可以利用一个平面, 移动到关于这个平面对称的点处. 每个平面在整个游戏过程中至多只能利用一次.
问此神到达终点花费的最少行动次数.

易知三个方向是不相关的. 所以只用先考虑一维的情形.
首先要想到, 走路和反射交替, 是等效于先反射完了再一口气走到终点的. 因为在反射之前的走动, 不会被反射动作放大. 反射前移动多少步, 经过若干次反射后所到达的位置, 与不移动直接反射到达的位置, 相差正好是移动的步数.
所以可以转化为先反射若干次, 再行走到终点. 现在就要推出反射到达的位置公式.
假设每个反射轴的坐标依次是x[1], x[2], ..., x[n], 神经过第k次反射后的位置是p[k].
容易推出, p[1] = 2x[1], p[2] = p[1] + 2(x[2]-x[1]) = 2x[2] - 2x[1], ... p[k] = 2x[k]-2x[k-1]+2x[k-2]-...+2*(-1)^(k-1)x[1].
这是很规则的正负交替求和, 正项数等于负项数, 或者比负项数多1.
到此问题转化得很清晰了: 在20个数中选出k个数作为正项, k(或k-1)个数作为负项, 每个数至多被选1次. 该方案的总行动次数是选出的个数(即做反射的总次数), 加上这些项之和到终点的距离(即最后一路走过去).
选数要降低复杂度, 可以把20个数分成两个集合, 每边10个数, 先各自生成2^10个和. 两边分别排序后, 从小到大枚举左边的, 记一个指针从大到小扫右边的.

[数学分治]

wolf5x 2011-07-30 11:04 发表评论

有向有环图的最小路径覆盖

Tue, 19 Jul 2011 14:42:00 GMT

本文纯属YY……

今天多校联合训练三的C题，http://acm.hdu.edu.cn/showproblem.php?pid=3861，题意归结起来是在一个有向图中求最小路径覆盖，也就是用尽量少的链去覆盖整个图，每个顶点必须属于且只能属于一条链。但是题意并未说明原图无环。标程解法是强连通分量缩点，再求有向无环图的最小路径覆盖。反例是：1->2,2->3,4->5,5->6,2->5,5->2。正解是2，123一组，456一组。

因为是要求路径数最小，所以YY了一个上下界最小流的做法。构图是将原来的点A0拆成两个，A和A'。从A到A'连一条边，下界和上界都为1。所有原来A0的出边，都从A'出去，下界0，上界1.所有原来A0的入边，都指向A。新建一个源点S，一个汇点T。从S到每个点A连一条边，下界0，上界1。从每个A'到T连一条边，下界0，上界1。

对这个新图求最小流，即为原题所求。

YY的证明：
A->A'，限制了这个点必须经过一次。这条边上的流量有两个来源：其它的点B'，或者源点S，前者说明A和B在同一条链中，B是A的前驱，后者说明A是链的起点。同样，这个流量有两个去处：其它的点C'，或者汇点T，前者说明A和C在同一条链中，C是A的后继，后者说明A是链的终点。

到达汇的每1单位流量，意味着一条链的终结。所以最小流就能让链数最少。

YY完毕，欢迎开炮……

ps. 理论上说，以上方法肯定是错的。要不然求Hamiltion通路就不是NP了＠。＠

wolf5x 2011-07-19 22:42 发表评论

srm 511 div1 500 1000

Sat, 02 Jul 2011 19:48:00 GMT

500pt FiveHundredEleven
给出N(N<=50)个不小于0且不大于511的整数. 开始时寄存器为0, 两人轮流选取一个数, 与寄存器的值OR, 把结果覆盖写入寄存器. 数不能重复使用. 如果某人操作之后寄存器的值为511, 或者轮到某人时数都取完了, 那么这个人就算负. 问先手是否有必胜策略.
容易想到2^9这一维, 记录当前每一位的0/1状态. 实际上, 不需要记录当前已经选过哪些数, 而只用记录已经选了几个数, 再由当前的0/1态, 就能推算出哪些数没选过. 有些数x满足x|now != x, 这些数肯定没选过. 而对那些x|now == x的数, 不必知道它具体的值, 因为它对后续操作的影响都一样, 就是延缓一步, 把局面原封不动地丢给对方. 所以只需知道当前还有多少个这样的x没被使用过, 这个值也能由上面的信息得到.
这样就是一个类似极大极小的必胜必败态记忆化搜索.
状态为dp[1<<9][N], 转移为N.

[状态DP]

1000pt GameOfLifeDivOne
一个长为N(N<=50)的串(环状, 首尾相连, 即x[N-1]与x[0]相连), 由'0', '1' 和'?'组成, 其中'?' 处可以填上'0'或'1'. 从T=0开始, 每过1单位时间, 整个串会更新一次: 某一位, 如果上一时刻, 它, 以及与它相邻的两位, 一共有至少2个'1', 那么这一时刻它变成'1', 否则它变成'0'. 问共有多少种填'?'的方法, 使得在经过T(T<=1000)时间后, 还有不少于K(K<=N)个'1'. 比如'101010'->'010101'->'101010'->...; '11010'->'11101'->'11111'->...

首先容易观察到, 两个或两个以上连续相同的位是永远不会变的. 只有01交替的子串才会发生变化. 所以任意一个串都可以看成是若干个形如 xpy的子串首尾连接而成, 而且两串的首尾要相同才能连起来, 就像[xp1y][yp2x][xp3x][xp4y].... 其中pk是01交替序列, x和y都是一位, 可能是'0'或'1'. 特别的,连续3个相同字符可以看成是xx和xx粘起来(有1位重叠). 对于一个首尾字符固定不变的01交替串, 它在T时间后有多少个'1'是很容易算的. 两头都是0的话, 如0101010->0010100->0001000, 每时间减少一个1; 两头都是1的话类似, 每时间增加一个1. 一头是0一头1, 则0和1的个数都不变, 如010101->001011->000111.
这样就有个算法的雏形, 类似背包: dp[pos][bit][one]表示: 从0到pos-1的子段, 以bit结尾, 且T时间后包含one个1的方法数. 如果从pos到某一位pos2-1, 能构造出以bit起始, 以bit2结束的交替串, 那么从状态dp[pos][bit][one]就能扩展到dp[pos2][bit2][one+one2], 则把前者加到后者上去, 其中one2是pos到pos2-1这个子串T时间后1的个数. 把原始串复制两遍, 就能比较方便地处理环.
枚举在原串中首次出现连续2个相同字符的位置startpos, 对每个startpos做一次上述DP. 把所有one>=K的方法数加起来即可. 此外要先预处理出任意edg[i][b1][j][b2], 即从i到j-1能否构造出以b1开始, b2结尾的交替串, 如果能, T时间后有多少个'1'.
其实整个题就是一道背包DP, 求用若干个短棍子, 拼出一个权值>=K的长棍子的方法数. 只是模型隐藏得很巧妙. orz...

[背包DP]

wolf5x 2011-07-03 03:48 发表评论

srm 507 div1 250 500 900

Tue, 31 May 2011 16:04:00 GMT

250p CubeStickers
给出若干个方形木板，每个木板有一种颜色。现在要选出其中6个，围出一个立方体。问是否可能使转出的立方体，任意两个相邻的面颜色不同。
直接按木板的总数分情况讨论就可以，但是我漏想了一种情况@.@
其实显然，同一种颜色最多能用两次，所以统计每种木板能用的个数之和,sigma(min(count[i],2))，和不小于6则可行。

500p CubePacking
给出Ns个边长为1的立方体和Nb个边长为L(2<=L<=10）的立方体。要找一个体积最小的长方体，使得可以把所有立方体堆进去。保证结果不超int32。
正是因为不超int32，所以可以直接枚举两条棱x,y，算第3条z的最小值。枚举时循环条件 x*x*x <= INF, x*y*y <= INF。计算z的最小值时要注意除法要向上取整，而且判断能否把边长为L的立方体都放进去的条件是(x/L)*(y/L)*(z/L) >= Nb，如果z小了，要加到足够大为止。
[枚举]

900p CubeBuilding
大小相同的红、绿、蓝色的立方体，分别给R、G、B个(R,G,B<=25)。把这些立方体全部搭积木一样的堆到N*N(N<=25)的格子棋盘中。可以在任意格子中堆任意高的立方体。规定一种方案是合法的，如果从北向南看的侧视图中只有一种颜色。问一共有多少种堆砌的方案。
可以先考虑N*1的棋盘，也就是侧视图中棋盘宽度是1。先考虑没有颜色的方块怎么放，再去染色。这样不管怎么堆，看到的方块数总是等于所有格子堆的最大高度，则需要固定颜色的方块数就为这个高度，剩下的方块可以任意染色。同理N*N的棋盘，需要固定颜色的方块数等于所有列中需要固定的数量之和。要求的答案就是，先枚举固定方块的数目，把它们染某一种颜色，剩下的方块可以用组合数直接算出有多少种染色方案，乘起来，最后求和。
关键就是要求出每一种固定方块数目的前提下，不考虑颜色，有多少种堆放方法。
由前面的讨论知道，可以先在N*1的棋盘上按行扩展，需要记录的状态是当前已使用的方块数，当前的最大高度。
然后利用这个结果按列扩展，记录的状态是当前已使用的方块数，当前已固定的方块数。
ps.染色之前的方案数只用求一次，之后分别把固定的方块染成3种不同颜色，只要用组合数分别算3次，加起来就行了。
O(9*N^5)的算法，时限有点紧。
[DP]

wolf5x 2011-06-01 00:04 发表评论

srm 506 div1 500

Thu, 12 May 2011 03:22:00 GMT

500pt
50个点的地图，从0开始按照顺序访问一系列点（不超过50个），访问顺序给出，一个点可能访问多次。某些点停着若干辆汽车。可以走路，也可以开车。开车的速度比走路快。但是限定一辆汽车只能使用一次，也就是下车后这辆车就作废。问按要求访问完所有点的最短总耗时。先floyd求每对点之间走路时间和开车时间。对于访问顺序中的每一步，使用每辆车都有个节省的时间。这就相当于建个二分图，左边x是访问顺序中的每一步，右边y是每一辆车。xi与yj的边权就是第i步使用第j辆车能节省的时间。最后结果就是总的走路时间减去最大权匹配。

[floyd最短路二分图最大权匹配]

wolf5x 2011-05-12 11:22 发表评论

srm 469 div1 250 500 1000

Sat, 29 May 2010 06:40:00 GMT

250p TheMoviesLevelOneDivOne
电影院有n行m列的座位, 有一些已经被预订了. 求在剩下的座位中, 选出同行且相邻的两个座位的方案数.
可以按行列将已预订的座位排序, 然后顺便扫一遍, 算出相邻两个被预订座位之间的方案数. 最后累加.
也可以用个set记录不能使用的方案, 再用没有预订座位的情况下的总方案数减去之.

500p TheMoviesLevelTwoDivOne
若干部电影, 每部电影有一个加血的时间点. 人看电影, 每看一分钟掉一点血. 血掉到0就结束. 问怎样按排顺序使看的电影部数最多. 如果总部数相同, 取字典序最小的解输出.
只有20部电影, 状态DP即可.
为保证字典序, 可以从后往前DP, 这样每次转移时新加入的电影都是当前最先看的, 保证它先择的是最小的, 即能保证字典序最小.

[DP]

1000p TheMoviesLevelThreeDivOne
若干部电影, A和B两人看每部电影的时间分别是A[i], B[i]. 初始安排, 要依次把第1,2,..,n部电影放入A或B的待看队列的队尾. A和B各自开始看自己队列中的电影, 看完一部后, 如果这是另一个人没看过的, 就加入它的队列中. 如果期间某人列队空了, 那么他就结束, 再也不看新电影了. 问有多少种初始安排方法, 能使A和B都能看完所有电影.
首先肯定不会出现一种安排使得A和B都卡. 因为A卡肯定发生在A看完他所有的电影之后, 且此时B没看完自己的, 所以B肯定不会卡.
这样就可以用总方案数2^N分别减去A卡的和B卡的方案数. 考虑A卡的情况. 假设A那一整坨东西的时长是sumA, B的第一个东西是tb1, 则A卡的条件是 sumA-tb1<0. 否则B看完tb1后把ta1加在sumA后面, 这时卡的条件是(sumA+ta1)-(tb1+tb2)<0. 依此, 如果在这过程中任意一次卡的条件符合, 那么后续怎么安排都是卡的. 于是用一维状态记录目前为止出现过的最小的X-Y, min, 还要一维记录当前的X-Y, cur, 以转移用. 转移时, 如果把当前电影放进A, 那么min和cur都增加A[i], 因为sumA增加了. 如果放进B, 那么用cur和B[i]来计算新的cur和min.
hint. cur=当前所有电影的A[i]的和-B中电影的B[i]的和, 新的min=除了新放的电影外所有放过的电影的A[i]的和-包括新电影在内的B中电影的B[i]的和.

ps. 1000的DP都很YD啊...

[DP]

wolf5x 2010-05-29 14:40 发表评论