在磕磕絆絆中，終于做完一百題，完成暑期目標(biāo)，會(huì)繼續(xù)加油...
附: summary (revision 37)
Summary of PKU solved, since 05-20-2010
------------------------Fighting-----------------------------
------------------------Fighting-----------------------------
[sort]
1002 487-3279
1007 DNA Sorting
1468 Rectangles
2299 Ultra-QuickSort
2388 Who's in the Middle
[search(dfs, bfs, backtracking)]
1020 Anniversary Cake [good]
1077 Eight [classic][bfs, bbfs, A*]
1101 The Game
1111 Image Perimeters [interesting]
1129 Channel Allocation [classic]
1164 The Castle
1166 The Clocks
1190 Birthday Cake [good]
1198 Solitaire [classic]
1321 Chessboard Problem
1416 Shredding Company
1426 Find The Multiple
1475 Pushing Boxes [complex]
1562 Oil Deposits
1606 Jugs
1629 Fillword
1691 Painting A Board
1724 ROADS
1753 Flip Game
1775 Sum of Factorials
1915 Knight Moves
1950 Dessert
2248 Addition Chains
2251 Dungeon Master
2488 A Knight's Journey
2531 Network Saboteur
2676 Sudoku
3009 Curling 2.0
3083 Children of the Candy Corn
3087 Shuffle'm Up
3126 Prime Path
3256 Cow Picnic
3278 Catch That Cow
3373 Changing Digits [hard]
3411 Paid Roads
3414 Pots
[dynamic programming/memory function]
1014 Dividing [good & hard]
1015 Jury Compromise
1050 To the Max [classic]
1080 Human Gene Functions
1088 Skiing [good]
1157 Little shop of flowers
1159 Palindrome
1160 Post Office [good]
1163 The Triangle
1179 Polygon [classic]
1185 Artillery position [classic, scdp]
1260 Pearls [good]
1276 Cash Machine [classic]
1458 Common Subsequence [classic]
1579 Function Run Fun
1631 Bridging signals
1887 Testing the CATCHER/2533 Longest Ordered Subsequence [classic]
1953 World Cup Noise
2192 Zipper
2250 Compromise
2479 Maximum sum/2593 Max Sequence
3356 AGTC
3624 Charm Bracelet
[greedy algorithm]
[data structure]
1028 Web Navigation (stack/array)
1611 The Suspects (union-find set)
1988 Cube Stacking (union-find set)
2524 Ubiquitous Religions (union-find set)
3253 Fence Repair (huffman tree)
3349 Snowflake Snow Snowflakes (Hash & Minimal Representation)
[graph algorithm]
[others]
1001 Exponentiation (high precision)
1008 Maya Calendar
1083 Moving Tables (novel perspective) [good]
1176 Party Lamps (enumerate)
1226 Substrings
1731 Orders (permutation) [good]
2080 Calendar
2244 Eeny Meeny Moo (Josephus Problem) [good]
2503 Babelfish (string hash)
2663 Tri Tiling (recurrence) [good]
[easy/water]
1000 A+B Problem
1003 Hangover
1004 Financial Management
1005 I Think I Need a Houseboat
1298 The Hardest Problem Ever
1316 Self Numbers
1477 Box of Bricks
1543 Perfect Cubes (build table)
1547 Clay Bully
1552 Doubles
1565 Skew Binary
1595 Prime Cuts
1936 All in All [good]
2081 Recaman's Sequence
2105 IP Address
2726 Holiday Hotel [funny]
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1111思路:
其實(shí)，這是一道簡(jiǎn)單題，關(guān)鍵是要看透如何求周長(zhǎng): 連通塊每格四個(gè)方向（上下左右）如果不在連通塊內(nèi)（超出范圍或者Empty）則周長(zhǎng)加一
DFS或者BFS都可以解決
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 21
5 #define is_valid(x,y) (x>=0 && x<row && y>=0 && y<col)
6 const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
7 const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
8 struct Point {
9 int x, y;
10 }queue[MAX_LEN*MAX_LEN];
11 char grid[MAX_LEN][MAX_LEN];
12 int visited[MAX_LEN][MAX_LEN];
13 int row, col, start_x, start_y;
14 int rt;
15
16 void
17 calculate(int x, int y)
18 {
19 int i, tmpx, tmpy;
20 for(i=0; i<4; i++) {
21 tmpx = x + dx[i];
22 tmpy = y + dy[i];
23 if(!is_valid(tmpx, tmpy) || grid[tmpx][tmpy]=='.')
24 ++rt;
25 }
26 }
27
28 void
29 bfs()
30 {
31 int i, head, tail, nxt_x, nxt_y;
32 head = -1;
33 tail = 0;
34 queue[tail].x = start_x-1;
35 queue[tail].y = start_y-1;
36 visited[start_x-1][start_y-1] = 1;
37 while(head < tail) {
38 ++head;
39 calculate(queue[head].x, queue[head].y);
40 for(i=0; i<8; i++) {
41 nxt_x = queue[head].x + dx[i];
42 nxt_y = queue[head].y + dy[i];
43 if(is_valid(nxt_x, nxt_y) && !visited[nxt_x][nxt_y] && grid[nxt_x][nxt_y]=='X') {
44 ++tail;
45 queue[tail].x = nxt_x;
46 queue[tail].y = nxt_y;
47 visited[nxt_x][nxt_y] = 1;
48 }
49 }
50 }
51 }
52
53 int
54 main(int argc, char **argv)
55 {
56 int i;
57 while(scanf("%d %d %d %d", &row, &col, &start_x, &start_y) != EOF) {
58 if(row==0 && col==0)
59 break;
60 for(i=0; i<row; i++)
61 scanf("%s", grid[i]);
62 rt = 0;
63 memset(visited, 0, sizeof(visited));
64 bfs();
65 printf("%d\n", rt);
66 }
67 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2244參考:
http://baike.baidu.com/view/213217.html?fromTaglist思路:
從這題認(rèn)識(shí)了經(jīng)典的約瑟夫問(wèn)題:
無(wú)論是用鏈表實(shí)現(xiàn)還是用數(shù)組實(shí)現(xiàn)都有一個(gè)共同點(diǎn)：要模擬整個(gè)游戲過(guò)程，不僅程序?qū)懫饋?lái)比較煩，而且時(shí)間復(fù)雜度高達(dá)O(nm)，當(dāng)n，m非常大(例如上百萬(wàn)，上千萬(wàn))的時(shí)候，幾乎是沒(méi)有辦法在短時(shí)間內(nèi)出結(jié)果的。我們注意到原問(wèn)題僅僅是要求出最后的勝利者的序號(hào)，而不是要讀者模擬整個(gè)過(guò)程。因此如果要追求效率，就要打破常規(guī)，實(shí)施一點(diǎn)數(shù)學(xué)策略。
為了討論方便，先把問(wèn)題稍微改變一下，并不影響原意：
問(wèn)題描述：n個(gè)人（編號(hào)0~(n-1))，從0開(kāi)始報(bào)數(shù)，報(bào)到(m-1)的退出，剩下的人繼續(xù)從0開(kāi)始報(bào)數(shù)。求勝利者的編號(hào)。
我們知道第一個(gè)人(編號(hào)一定是m%n-1) 出列之后，剩下的n-1個(gè)人組成了一個(gè)新的約瑟夫環(huán)（以編號(hào)為k=m%n的人開(kāi)始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且從k開(kāi)始報(bào)0。
現(xiàn)在我們把他們的編號(hào)做一下轉(zhuǎn)換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
變換后就完完全全成為了(n-1)個(gè)人報(bào)數(shù)的子問(wèn)題，假如我們知道這個(gè)子問(wèn)題的解：例如x是最終的勝利者，那么根據(jù)上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況的解嗎？！！變回去的公式很簡(jiǎn)單，相信大家都可以推出來(lái)：x'=(x+k)%n
如何知道(n-1)個(gè)人報(bào)數(shù)的問(wèn)題的解？對(duì)，只要知道(n-2)個(gè)人的解就行了。(n-2)個(gè)人的解呢？當(dāng)然是先求(n-3)的情況 ---- 這顯然就是一個(gè)倒推問(wèn)題！好了，思路出來(lái)了，下面寫(xiě)遞推公式：
令f[i]表示i個(gè)人玩游戲報(bào)m退出最后勝利者的編號(hào)，最后的結(jié)果自然是f[n]
遞推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了這個(gè)公式，我們要做的就是從1-n順序算出f[i]的數(shù)值，最后結(jié)果是f[n]。因?yàn)閷?shí)際生活中編號(hào)總是從1開(kāi)始，我們輸出f[n]+1
由于是逐級(jí)遞推，不需要保存每個(gè)f[i]，程序也是異常簡(jiǎn)單：
#include <stdio.h>
int main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}
這個(gè)算法的時(shí)間復(fù)雜度為O(n)，相對(duì)于模擬算法已經(jīng)有了很大的提高。算n，m等于一百萬(wàn)，一千萬(wàn)的情況不是問(wèn)題了。可見(jiàn)，適當(dāng)?shù)剡\(yùn)用數(shù)學(xué)策略，不僅可以讓編程變得簡(jiǎn)單，而且往往會(huì)成倍地提高算法執(zhí)行效率。
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4
5 /*
6 * f[1] = 0
7 * f[i] = (f[i-1]+m)%i
8 */
9 int
10 josephus(int n, int m)
11 {
12 int i, s = 0;
13 for(i=2; i<=n; i++)
14 s = (s+m)%i;
15 return s+1;
16 }
17
18 int
19 main(int argc, char **argv)
20 {
21 int n, m;
22 while(scanf("%d", &n)!=EOF && n!=0) {
23 m = 2;
24 /* because first cut off city 1 and then begins every mth */
25 while(josephus(n-1, m) != 1)
26 ++m;
27 printf("%d\n", m);
28 }
29 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1260思路:
簡(jiǎn)單DP，但是就是想不到...
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 101
5 #define INF 0x7FFFFFFF
6 #define min(a,b) ((a)<(b) ? (a) : (b))
7 int num[MAX_LEN], price[MAX_LEN];
8 int sum[MAX_LEN]; /* aux */
9 int table[MAX_LEN];
10 int c;
11
12 /*
13 * f[i] represent the lowest possible price needed to buy list[1..i], so:
14 * f[i] = min (f[k] + (num[k+1]+
+num[i]+10)*price[i]), 0<=k<i-1
15 */
16 int
17 dp()
18 {
19 int i, k, tmp;
20 sum[0] = 0;
21 for(i=1; i<=c; i++)
22 sum[i] = sum[i-1]+num[i];
23 table[0] = 0;
24 for(i=1; i<=c; i++) {
25 table[i] = INF;
26 for(k=0; k<=i-1; k++) {
27 tmp = table[k] + (sum[i]-sum[k]+10)*price[i];
28 table[i] = min(table[i], tmp);
29 }
30 }
31 return table[c];
32 }
33
34 int
35 main(int argc, char **argv)
36 {
37 int i, tests;
38 scanf("%d", &tests);
39 while(tests--) {
40 scanf("%d", &c);
41 for(i=1; i<=c; i++)
42 scanf("%d %d", num+i, price+i);
43 printf("%d\n", dp());
44 }
45 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1179思路:
這題輸在了對(duì)原題目的理解和分析上，沒(méi)能成功地走出第一步:
將原題解析成對(duì)于表達(dá)式的求解
把缺了一條邊的多邊形展開(kāi)成直線就是一個(gè)表達(dá)式
注意：為了求乘法，必須同時(shí)保存最大值和最小值
f[i][j]記錄表達(dá)式中從頂點(diǎn)i到頂點(diǎn)j這段子表達(dá)式的值
動(dòng)態(tài)規(guī)劃的思想類似于矩陣連乘
參考:
http://hi.baidu.com/xiehuixb/blog/item/575ec81e221466c1a786699e.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 51
5 #define INF 9223372036854775807LL
6 #define maximal(a, b) ((a)>(b) ? (a) : (b))
7 #define minimal(a, b) ((a)<(b) ? (a) : (b))
8 char operand[MAX_LEN][2];
9 int operators[MAX_LEN];
10 int n, ans_len, ans[MAX_LEN];
11 long long int rt, max[MAX_LEN][MAX_LEN], min[MAX_LEN][MAX_LEN];
12
13 /*
14 * when it comes to: '+'
15 * max[i][j] = maximal(max[i][k] + max[k+1][j])
16 * min[i][j] = minimal(min[i][k] + min[k+1][j])
17 *
18 * when it comes to: '*'
19 * max[i][j] = maximal(max[i][k]*max[k+1][j], max[i][k]*min[k+1][j], min[i][k]*max[k+1][j], min[i][k]*min[k+1][j])
20 * min[i][j] = minimal(max[i][k]*max[k+1][j], max[i][k]*min[k+1][j], min[i][k]*max[k+1][j], min[i][k]*min[k+1][j])
21 *
22 * i<=k<j
23 */
24 void
25 solve(char *opd, int *ops, int del_edge)
26 {
27 int i, j, k, len;
28 for(i=1; i<=n; i++)
29 max[i][i] = min[i][i] = ops[i];
30 for(len=2; len<=n; len++) {
31 for(i=1; i<=n-len+1; i++) {
32 j = i+len-1;
33 max[i][j] = -INF;
34 min[i][j] = INF;
35 for(k=i; k<j; k++) {
36 if(opd[k] == 't') {
37 max[i][j] = maximal(max[i][j], max[i][k]+max[k+1][j]);
38 min[i][j] = minimal(min[i][j], min[i][k]+min[k+1][j]);
39 } else { /* opd[k] == 'x' */
40 max[i][j] = maximal(max[i][j], max[i][k]*max[k+1][j]);
41 max[i][j] = maximal(max[i][j], max[i][k]*min[k+1][j]);
42 max[i][j] = maximal(max[i][j], min[i][k]*max[k+1][j]);
43 max[i][j] = maximal(max[i][j], min[i][k]*min[k+1][j]);
44
45 min[i][j] = minimal(min[i][j], max[i][k]*max[k+1][j]);
46 min[i][j] = minimal(min[i][j], max[i][k]*min[k+1][j]);
47 min[i][j] = minimal(min[i][j], min[i][k]*max[k+1][j]);
48 min[i][j] = minimal(min[i][j], min[i][k]*min[k+1][j]);
49 }
50 }
51 }
52 }
53 if(max[1][n] >= rt) {
54 if(max[1][n] == rt)
55 ans[ans_len++] = del_edge;
56 else {
57 rt = max[1][n];
58 ans_len = 0;
59 ans[ans_len++] = del_edge;
60 }
61 }
62 }
63
64 int
65 main(int argc, char **argv)
66 {
67 int i, j, k;
68 char tmpopd[MAX_LEN];
69 int tmpops[MAX_LEN];
70 while(scanf("%d", &n) != EOF) {
71 for(i=1; i<=n; i++)
72 scanf("%s%d", operand[i], operators+i);
73 rt = -INF;
74 ans_len = 0;
75 for(i=1; i<=n; i++) {
76 for(j=i%n+1, k=1; j!=i; j=j%n+1, k++)
77 tmpopd[k] = operand[j][0];
78 tmpopd[k] = '\0';
79 tmpops[1] = operators[i];
80 for(j=i%n+1, k=2; j!=i; j=j%n+1, k++)
81 tmpops[k] = operators[j];
82 solve(tmpopd, tmpops, i);
83 }
84 printf("%lld\n", rt);
85 for(i=0; i<ans_len; i++)
86 printf("%d ", ans[i]);
87 printf("\n");
88 }
89 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2663思路:
參考:
http://www.tkz.org.ru/2009-07/poj-2663-tri-tiling/遞推題。經(jīng)典。
本題是POJ2506 Tiling的威力加強(qiáng)版。由兩行變成了三行。
推導(dǎo)過(guò)程與POJ2506異曲同工。
opt[i]=3*opt[i-2]+2*opt[i-4]+2*opt[i-6]+2*opt[i-8]+……直到方括號(hào)內(nèi)表達(dá)式的值為0。
解釋一下，3*opt[i-2]是最右邊有三行2列的三種情況。
后面的2*opt[i-X]，則是最右邊有X列類似以下的結(jié)構(gòu)的情況：
X=4列的情況：
；X=6列的情況
；等等等等
以上情況可以上下顛倒，故每種情況又有兩種表示，所以需要乘以2。而以上的情況從4開(kāi)始，然后每次遞增2，所以遞推式中這部分從i-4開(kāi)始（如果大等于0的話），每次遞減2。
如果i為奇數(shù)，稍微推一下，可得，奇數(shù)的列數(shù)無(wú)解，答案為0。
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 31
5 long table[MAX_LEN];
6
7 void
8 build_table()
9 {
10 int i, j, sum;
11 memset(table, 0, sizeof(table));
12 table[0] = 1;
13 table[2] = 3;
14 for(i=4; i<MAX_LEN; i=i+2) {
15 sum = 3*table[i-2];
16 for(j=4; i-j>=0; j=j+2)
17 sum += (table[i-j]<<1);
18 table[i] = sum;
19 }
20 }
21
22 int
23 main(int argc, char **argv)
24 {
25 int n;
26 build_table();
27 while(scanf("%d", &n)!=EOF && n!=-1) {
28 printf("%ld\n", table[n]);
29 }
30 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1157思路:
比較容易的動(dòng)態(tài)規(guī)劃，這里提供兩種思路，其中第二種更優(yōu)
另外，居然在寫(xiě)代碼的時(shí)候?qū)?xFFFFFFFF當(dāng)作最小的int值，汗...
代碼(方案1)
1 /* 63MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_F 101
6 #define MAX_V 101
7 #define INF 0xF0000000
8 int values[MAX_F][MAX_V];
9 int table[MAX_F][MAX_V];
10 int f, v;
11
12 /*
13 * f[i][j] represent the maximum aesthetic values for putting the first [1..i]
14 * bunches in the first [1..j] vases, so:
15 * f[i][j] = max (f[i-1][k] + tmp), i-1<=k<j
16 */
17 dp()
18 {
19 int i, j, k, p, t, up, tmp, max;
20 table[1][1] = values[1][1];
21 for(j=2; j<=v-f+1; j++) /* i = 1 */
22 table[1][j] = values[1][j]>table[1][j-1] ? values[1][j] : table[1][j-1];
23 for(i=2; i<=f; i++) {
24 up = v-f+i;
25 for(j=i; j<=up; j++) {
26 max = INF;
27 for(k=i-1; k<j; k++) {
28 t = values[i][k+1];
29 for(p=k+2; p<j; p++)
30 t = values[i][p] > t ? values[i][p] : t;
31 tmp = table[i-1][k] + t;
32 max = tmp > max ? tmp : max;
33 }
34 table[i][j] = max;
35 }
36 }
37 return table[f][v];
38 }
39
40 int
41 main(int argc, char **argv)
42 {
43 int i, j;
44 while(scanf("%d %d", &f, &v)!=EOF) {
45 for(i=1; i<=f; i++)
46 for(j=1; j<=v; j++)
47 scanf("%d", values[i]+j);
48 printf("%d\n", dp());
49 }
50 }
代碼(方案2)
1 /* 32MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_F 101
6 #define MAX_V 101
7 #define INF 0xF0000000
8 int values[MAX_F][MAX_V];
9 int table[MAX_F][MAX_V];
10 int f, v;
11
12 /*
13 * f[i][j] represent the maximum aesthetic values for putting the i(th) bunch
14 * in the j(th) vases(total i bunches), so:
15 * f[i][j] = max(f[i-1][k])+values[i][j], i-1<=k<j
16 */
17 dp()
18 {
19 int i, j, k, up, max, rt;
20 for(j=1; j<=v-f+1; j++)
21 table[1][j] = values[1][j];
22 for(i=2; i<=f; i++) {
23 up = v-f+i;
24 for(j=i; j<=up; j++) {
25 max = INF;
26 for(k=i-1; k<j; k++)
27 max = table[i-1][k] > max ? table[i-1][k] : max;
28 table[i][j] = max+values[i][j];
29 }
30 }
31 rt = INF;
32 for(j=f; j<=v; j++)
33 rt = table[f][j]>rt ? table[f][j] : rt;
34 return rt;
35 }
36
37 int
38 main(int argc, char **argv)
39 {
40 int i, j;
41 while(scanf("%d %d", &f, &v)!=EOF) {
42 for(i=1; i<=f; i++)
43 for(j=1; j<=v; j++)
44 scanf("%d", values[i]+j);
45 printf("%d\n", dp());
46 }
47 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1731思路:
求全排列，這個(gè)問(wèn)題本身挺簡(jiǎn)單，不過(guò)題目要求: a. 不能重復(fù)；b. 有序輸出
記得曾經(jīng)做過(guò)這題，當(dāng)時(shí)偷懶用STL過(guò)的(真要自己寫(xiě)，估計(jì)當(dāng)時(shí)也不會(huì)(*^__^*) 嘻嘻……)
現(xiàn)在，決心棄用C++來(lái)做題，好好鍛煉基本功，所以就硬著頭皮自己慢慢寫(xiě)
好在前段時(shí)間對(duì)于搜索題有了一定的積累，否則相信自己肯定還是不知道怎么寫(xiě)的
找個(gè)例子，畫(huà)出遞歸調(diào)用樹(shù)，對(duì)于理解有很大幫助
純C遞歸實(shí)現(xiàn)如下:
代碼:
1 /* 364K 454MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 201
6 char str[MAX_LEN];
7 int len;
8
9 int
10 compare(const void *arg1, const void *arg2) /* for qsort */
11 {
12 return *((char *)arg1) - *((char *)arg2);
13 }
14
15 void
16 swap(char *seq, int i, int j) /* exchange */
17 {
18 char tmp = seq[i];
19 seq[i] = seq[j];
20 seq[j] = tmp;
21 }
22
23 void
24 perm(char *seq, int begin, int end)
25 {
26 int i, j, tmp;
27 char pre=0;
28 if(begin >= end) {
29 printf("%s\n", seq);
30 return;
31 }
32 for(i=begin; i<=end; i++) {
33 if(i>begin && seq[i]==seq[begin]) /* avoid duplicates */
34 continue;
35 if(pre == seq[i]) /* avoid duplicate */
36 continue;
37 /* in order to keep the alphabetical order */
38 tmp = seq[i];
39 for(j=i; j>begin; j--)
40 seq[j] = seq[j-1];
41 seq[begin] = tmp;
42 perm(seq, begin+1, end);
43 tmp = seq[begin];
44 for(j=begin; j<i; j++)
45 seq[j] = seq[j+1];
46 seq[i] = tmp;
47 /*
48 swap(seq, begin, i);
49 perm(seq, begin+1, end);
50 swap(seq, begin, i);
51 */
52 pre = seq[i];
53 }
54 }
55
56 int
57 main(int argc, char **argv)
58 {
59 while(scanf("%s", str) != EOF) {
60 len = strlen(str);
61 qsort(str, len, sizeof(char), compare);
62 perm(str, 0, len-1);
63 }
64 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1631思路:
題意理解清楚，其實(shí)就是找出最長(zhǎng)上升子序列
這里采用O(nlogn)的算法，類似于貪心的原理，關(guān)鍵是要理解輔助數(shù)組aux[]的含義，aux[len]所代表的是組成長(zhǎng)度為len的最長(zhǎng)上升子序列的尾元素的最小值
下面的內(nèi)容轉(zhuǎn)自:
http://blog.csdn.net/ottoCho/archive/2009/12/02/4927262.aspxO(n*log n)算法分析如下：
設(shè) A[t]表示序列中的第t個(gè)數(shù)，F(xiàn)[t]表示從1到t這一段中以t結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度，初始時(shí)設(shè)F [t] = 0(t = 1, 2, ..., len(A))。則有動(dòng)態(tài)規(guī)劃方程：F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。
現(xiàn)在，我們仔細(xì)考慮計(jì)算F[t]時(shí)的情況。假設(shè)有兩個(gè)元素A[x]和A[y]，滿足
(1)x < y < t (這里應(yīng)該錯(cuò)了，如果x<y<t成立，那么F[y]>=F[x]+1，不可能有(3)成立，這里應(yīng)該是y<x<t) [by simplyzhao, 2010-10-19]
(2)A[x] < A[y] < A[t]
(3)F[x] = F[y]
此時(shí)，選擇F[x]和選擇F[y]都可以得到同樣的F[t]值，那么，在最長(zhǎng)上升子序列的這個(gè)位置中，應(yīng)該選擇A[x]還是應(yīng)該選擇A[y]呢？
很明顯，選擇A[x]比選擇A[y]要好。因?yàn)橛捎跅l件(2)，在A[x+1] ... A[t-1]這一段中，如果存在A[z]，A[x] < A[z] < a[y]，則與選擇A[y]相比，將會(huì)得到更長(zhǎng)的上升子序列。
再根據(jù)條件(3)，我們會(huì)得到一個(gè)啟示：根據(jù)F[]的值進(jìn)行分類。對(duì)于F[]的每一個(gè)取值k，我們只需要保留滿足F[t] = k的所有A[t]中的最小值。設(shè)D[k]記錄這個(gè)值，即D[k] = min{A[t]} (F[t] = k)。
注意到D[]的兩個(gè)特點(diǎn)：
(1) D[k]的值是在整個(gè)計(jì)算過(guò)程中是單調(diào)不上升的。
(2) D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。
利 用D[]，我們可以得到另外一種計(jì)算最長(zhǎng)上升子序列長(zhǎng)度的方法。設(shè)當(dāng)前已經(jīng)求出的最長(zhǎng)上升子序列長(zhǎng)度為len。先判斷A[t]與D[len]。若A [t] > D[len]，則將A[t]接在D[len]后將得到一個(gè)更長(zhǎng)的上升子序列，len = len + 1， D[len] = A [t]；否則，在D[1]..D[len]中，找到最大的j，滿足D[j] < A[t]。令k = j + 1，則有A [t] <= D[k]，將A[t]接在D[j]后將得到一個(gè)更長(zhǎng)的上升子序列，更新D[k] = A[t]。最后，len即為所要求的最長(zhǎng)上 升子序列的長(zhǎng)度。
在 上述算法中，若使用樸素的順序查找在D[1]..D[len]查找，由于共有O(n)個(gè)元素需要計(jì)算，每次計(jì)算時(shí)的復(fù)雜度是O(n)，則整個(gè)算法的 時(shí)間復(fù)雜度為O(n^2)，與原來(lái)的算法相比沒(méi)有任何進(jìn)步。但是由于D[]的特點(diǎn)(2)，我們?cè)贒[]中查找時(shí)，可以使用二分查找高效地完成，則整個(gè)算法 的時(shí)間復(fù)雜度下降為O(nlogn)，有了非常顯著的提高。需要注意的是，D[]在算法結(jié)束后記錄的并不是一個(gè)符合題意的最長(zhǎng)上升子序列！
代碼:
1 /* O(nlogn) algorithm: the longest increasing sub-sequence [LIS] */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 40001
6 int num[MAX_LEN];
7 int aux[MAX_LEN];
8 int size, rt_len;
9
10 int
11 dp()
12 {
13 int i, left, right, mid;
14 rt_len = 1;
15 aux[rt_len] = num[0];
16 for(i=1; i<size; i++) {
17 if(num[i] > aux[rt_len]) {
18 ++rt_len;
19 aux[rt_len] = num[i];
20 } else {
21 /* binary search: O(logn) */
22 left = 1;
23 right = rt_len;
24 while(left <= right) {
25 mid = (left+right)/2;
26 if(num[i]>aux[mid])
27 left = mid+1;
28 else
29 right = mid-1;
30 }
31 aux[left] = num[i];
32 }
33 }
34 return rt_len;
35 }
36
37 int
38 main(int argc, char **argv)
39 {
40 int i, tests;
41 scanf("%d", &tests);
42 while(tests--) {
43 scanf("%d", &size);
44 for(i=0; i<size; i++)
45 scanf("%d", num+i);
46 printf("%d\n", dp());
47 }
48 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1887http://acm.pku.edu.cn/JudgeOnline/problem?id=2533思路:
典型而簡(jiǎn)單的動(dòng)態(tài)規(guī)劃，類似于最大子段和的思想:
f[i]表示以num[i]結(jié)尾的最長(zhǎng)下降(上升)子序列，那么:
f[i] = max (f[j]+1, if num[j]>num[i] && 0<=j<i)
原本挺簡(jiǎn)單的代碼，一會(huì)就寫(xiě)完了，結(jié)果卻因?yàn)橐粋€(gè)臨時(shí)變量的初始化錯(cuò)誤而WA了好多次，要細(xì)心...
上述是O(n^2)的算法，另外還有O(nlgn)的算法，下回嘗試。
代碼(pku 1887):
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 32767
5 int num[MAX_LEN];
6 int max[MAX_LEN];
7 int len;
8
9 /*
10 * f[i] represent the longest descent sequence ended with num[i], so:
11 * f[i] = max ( f[j]+1, if num[j]>num[i], 0<=j<i)
12 */
13 int
14 dp()
15 {
16 int i, j, t, rt;
17 max[0] = rt = 1;
18 for(i=1; i<len; i++) {
19 t = 1; /* WA twice here, for t=-1 */
20 for(j=0; j<i; j++) {
21 if(num[j] > num[i])
22 t = max[j]+1>t ? max[j]+1 : t;
23 }
24 max[i] = t;
25 rt = max[i]>rt ? max[i] : rt;
26 }
27 return rt;
28 }
29
30 int
31 main(int argc, char **argv)
32 {
33 int i, tmp, cnt = 0;
34 while(scanf("%d", &tmp)!=EOF && tmp!=-1) {
35 num[0] = tmp;
36 len = 1;
37 while(scanf("%d", num+len)!=EOF && num[len]!=-1)
38 ++len;
39 printf("Test #%d:\n maximum possible interceptions: %d\n\n", ++cnt, dp());
40 }
41 }