posts - 43,  comments - 9,  trackbacks - 0
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(intvoid(*)(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)]}.

posted @ 2011-08-31 13:07 wolf5x 阅读(136) | 评论 (0)编辑 收藏
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中所有"计数<S中已处理点个数"的, 都可以确定是连通的, 把它们从T中删除, 加入S中.
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 }
posted @ 2011-08-15 03:06 wolf5x 阅读(314) | 评论 (0)编辑 收藏
250pt MagicalGirlLevelOneDivOne
某神在(0,0)处, 需要走到(x,y)处(0<x,y<=10^9), 他只能按类似马跳的方式走, 即, 给出一个n, 他可以从(a,b)走到(a-1,b-n) (a+1,b-n) (a-1,b+n) (a+1,b+n) (a-n,b-1) (a+n,b-1) (a-n,b+1) (a+n, b+1) 中的一个.现在给出50个不同的n[1..50], 他可以以任意的n[i]方式走, 每种方式的使用次数不限. 问能否走到目的地(x,y).

很明显, 此神可以沿任意方向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<<m], 前n行, 每一列和的奇偶性对应bit为0或1. O(1<<m)的转移复杂度, 转移时要注意该行状态1有奇数个.

觉得是道很好的题, 状态设计很巧妙...

[状态DP 状态压缩设计]

900pt MagicalGirlLevelThreeDivOne
某神给出K(K<=50)个01串, 每个串的长度不超过50. 用这些串组成新的串放到数组A[]里. 如果i<K, 则A[i]为给出的第i个串. 否则A[i] = A[i-1] + A[i-K-1] + A[i-2*K-1] + ... + A[i-p*K-1], 其中p是使i-p*K-1>=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)如果hi<len[id-1], 则递归查询(id-1, lo, hi).
4)否则两个儿子都要查询, 并根据返回的结果求当前区间的结果.

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

[分治 复杂度分析]

posted @ 2011-08-10 14:30 wolf5x 阅读(1168) | 评论 (1)编辑 收藏
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个和. 两边分别排序后, 从小到大枚举左边的, 记一个指针从大到小扫右边的.

[数学 分治]
posted @ 2011-07-30 11:04 wolf5x 阅读(178) | 评论 (0)编辑 收藏
本文纯属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了@。@
posted @ 2011-07-19 22:42 wolf5x 阅读(683) | 评论 (0)编辑 收藏
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]

posted @ 2011-07-03 03:48 wolf5x 阅读(276) | 评论 (0)编辑 收藏
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]
posted @ 2011-06-01 00:04 wolf5x 阅读(168) | 评论 (0)编辑 收藏
500pt
50个点的地图,从0开始按照顺序访问一系列点(不超过50个),访问顺序给出,一个点可能访问多次。某些点停着若干辆汽车。可以走路,也可以开车。开车的速度比走路快。但是限定一辆汽车只能使用一次,也就是下车后这辆车就作废。问按要求访问完所有点的最短总耗时。 先floyd求每对点之间走路时间和开车时间。对于访问顺序中的每一步,使用每辆车都有个节省的时间。这就相当于建个二分图,左边x是访问顺序中的每一步,右边y是每一辆车。xi与yj的边权就是第i步使用第j辆车能节省的时间。 最后结果就是总的走路时间减去最大权匹配。

[floyd最短路 二分图最大权匹配]
posted @ 2011-05-12 11:22 wolf5x 阅读(206) | 评论 (0)编辑 收藏
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]
posted @ 2010-05-29 14:40 wolf5x 阅读(230) | 评论 (0)编辑 收藏
仅列出标题  下一页
<2021年1月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜