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)]}.
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 }
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, 偶依然蒻爆了.
[分治 復雜度分析]
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個和. 兩邊分別排序后, 從小到大枚舉左邊的, 記一個指針從大到小掃右邊的.
[數學 分治]
本文純屬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了＠。＠
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]
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]
500pt
50個點的地圖，從0開始按照順序訪問一系列點（不超過50個），訪問順序給出，一個點可能訪問多次。某些點停著若干輛汽車。可以走路，也可以開車。開車的速度比走路快。但是限定一輛汽車只能使用一次，也就是下車后這輛車就作廢。問按要求訪問完所有點的最短總耗時。
先floyd求每對點之間走路時間和開車時間。對于訪問順序中的每一步，使用每輛車都有個節省的時間。這就相當于建個二分圖，左邊x是訪問順序中的每一步，右邊y是每一輛車。xi與yj的邊權就是第i步使用第j輛車能節省的時間。
最后結果就是總的走路時間減去最大權匹配。
[floyd最短路 二分圖最大權匹配]
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]