冗余的代码

Zoj 2546 Walk Though the Forest

stcrux — 2008-03-02 15:36:00

2767343 2008-03-02 15:15:48 Accepted 2546 C++ 00:00.45 4364K C.D.=.= 写了个最简单的单源路径算法。完全是O(V^2)。比起2281的最小堆+链表差了不止一个档次…… 后续还有一个记忆化搜索的处理，当value[u]>value[v]的时候可以把u的路径可能数加到v上。Waterloo的那一次LC还比较简单，加上网站提供标程与数据，已经轻松Clear。 1#include 2#include 3 4#define MAXN 200000000 5 6int N, M, value[1001], visited[1001], a[1001][1001], num[1001]; 7 8int init (); 9void dijk ();10void dp ();11int func ( int );1213int main ()14{15 //freopen ( "in.txt", "r", stdin );16 while ( init () )17 {18 dijk ();19 dp ();20 //print ();21

Zoj 2704 Breckets

stcrux — 2008-02-26 19:32:00

2761956 2008-02-26 19:16:05 Accepted 2704 C++ 00:00.14 924K C.D.=.= 犯了一个极其低级的错误，把l = strlen(str); for ( i = 0; i < l; i ++ )写成了for ( i = 0; i < strlen ( str ); i ++ )，结果超时无数次。当for循环足够大时，不起眼的地方积累起来，错误也会变得很显著。起初想到可能是使用STL导致的超时，于是把栈简单模拟，结果仍然。看来对这种地方还是不够敏感啊。 1#include 2#include 3 4char str[100001]; 5int s[100001], top; 6 7void pt (); 8void print ( int, int ); 9 10int main () 11{ 12 // '(' -1 ')' -2 '[' -3 ']' -4 13 //freopen ( "in.txt", "r", stdin ); 14 while ( scanf ( "%s", str ) != EOF ) 15 { 16 &n

Zoj 1013 Great Equipment

stcrux — 2008-02-21 19:09:00

2756964 2008-02-21 18:12:06 Accepted 1013 C++ 00:03.02 2404K C.D.=.= 有点意思的DP题，同样也有不小的难度。模型大致如下：一组背包，除了体积以外，还有重量的限制。有3种不同的item：比如说一把剑，一件盔甲，一双鞋。他们各自有体积，重量，Def值，而组合到一起——也许叫做不死斗篷，出题者明显是英雄无敌的爱好者——又有新的Def加成。如何得到最大的Def？对于每一辆车（背包），在装满的情形下，可以得到几组不同的xyz，代表三种装备的数量。假如能够得到所有车子总的xyz组合，这题就迎刃而解了。但是我们不能对100辆车子，对每种xyz之和进行搜索，这样数据量太大。考虑到题目给出xyz<500，故而建立m[i][x][y]的数组，对前i辆车中的xy进行DP。因为在当前i车中，对于每组ix iy，都有唯一对应的iz（最大）。而只要把这辆车中的ixiy去掉就是前一辆车i-1下的xyz值，所以m[i][x][y] =MAX（m[i - 1][x - ix][y - iy]+iz），ix iy 遍历，表示在前i辆车中z能达到的最大值。从而所有的xyz组合都被记录下来了。这种用N-1维数组记录一个N维组合，然后对其DP求得最后一个数的方法就很棒。为了节省空间，采用滚动数组。具体代码中把i-1提前，对于i-1下每一组xy，加上这辆车里的ixiy就是当前i组下的xy。 #include #include #define min(x, y) ( x < y ? x : y )#define rg(x, y) ( x = ( y > x ? y : x ) ) //replace if greaterint N, c1, c2, c3, de

GPU==CPU？

stcrux — 2008-02-19 19:57:00

看到这个熟悉而陌生的画面，我彻底囧了。我知道现在的GPU两个频率都有向CPU靠拢的趋势，但我就料不到N打算把它移植到手机上去呀。据说可以放高清视频的手机芯片：APX 2500，和微软合作开发，频率高达750MHZ。高中网吧里战Quake的时候，用的也只不过是赛扬667…… http://www.pcpop.com/doc/0/269/269867.shtml

Zoj 2527 Series

stcrux — 2008-02-19 19:30:00

2755219 2008-02-19 18:56:56 Accepted 2527 C++ 00:00.07 4364K C.D. 做了两天题后有点头昏脑胀，上星期连着熬夜看联盟杯的后遗症不失时机地蹦出来张牙舞爪。也罢，这个礼拜要好好休息，不看冠军杯了。（其实上个赛季也都是看Bt录播，人懒没药医 =.= ）一道简单的DP。难点在于原来的算法时间复杂度O(N^3)，N=1000。题目描述相当简单，给定一个数组，求其中最长的等差数列的长度。首先考虑一维规划。显然不行，一个等差数列不能用一个数字进行定义。转而考虑二维。当数列的差不大时，可以考虑用F(i,d)表示当前一个数a[i]下等差为d的数列长度。可是这个数列给出了1e10的范围…… 继续转进。F(i,j)表示数列的最后一个数是a[i],倒数第二个是a[j]。这样就保存了等差，也可以求得倒数第三个数，前提是找得到。只要在数组里找到它的位置k，就可以继续方程式：F(i,j) = F(j,k) + 1。但是这样一来无疑要遍历整个数组，使O上升到N^3，这太慢了。为此先对整个数组排序，去除重复的数字，然后在有序的数组里可以用二分搜索k。O(N^2*log(N))，完全满足时间要求。 #include #include #include int b[1001][1001], a[1001], N, ans;int cmp ( const void *a, const void *b ){ return *( int * ) a > *( int * ) b;}int init ();int b_search ( int, int, int );void dp ();int&nbs

Zoj 2740 Message System

stcrux — 2008-02-17 16:50:00

2753473 2008-02-17 16:25:45 Accepted 2740 C++ 00:00.00 436K C.D. 世界上最郁闷的事情，不是连续五个WA，而是连续莫名其妙的WA，却不知道错在哪里；比这更郁闷的事情，是改动之后的连续五个AC，却发现再也找不到刚才究竟错在哪里…… 遥想当年，浙大初赛时，雄姿英发；谈笑间，代码灰飞烟灭。故题重做，多情应笑我，迟来三年。卡了近三年的题目，回过头来再看也是一道简单题。求图是否为连通生成树。预处理边数M，然后用并查集检查一下是否有回路，马上就可以解决。因为满足生成树的情况下，M恒等于点数N-1，所以在预处理后就不需要考虑是否所有点都能够被访问。开始的时候写了一个BFS算法，遍历，结果失败。（我果然还是比较菜……= =） #include #include int N, M, p[1001], num[1001];int init ();void init_set ();int find_set ( int );int union_set ( int, int );int main (){ //freopen ( "in.txt", "r", stdin ); while ( init () ) { } return 0;}void init_set (){ int i; for ( i = 1; i <=&

Zoj 2107 Quoit Design

stcrux — 2008-02-14 14:03:00

2750801 2008-02-14 13:48:15 Accepted 2107 C++ 00:02.95 4068K C.D. 分治算法的应用。在求左和右之间的最短点对时，先把满足X坐标差值小于CurMin的点对按Y排序，然后可以剪掉Y坐标值差小于CurMin的点对。 /**//* 作者 Crux.D 日期 2008.2.14 描述分治求最短距离点对*/#include #include #include #include typedef struct{ double x, y;} Point;Point p[100001];int N, q[100000];int init ();double b_search ( int, int );inline double dist ( int i, int j ){ double x = sqrt ( ( p[i].x - p[j].x ) * ( p[i].x - p[j].x ) + &n

Zoj 2279 In the Mirror

stcrux — 2008-02-13 18:21:00

一道很好的搜索题。WA一次，原因是二进制hash开的太小。一般求最短步数的问题，大多采用BFS，当终点与当前节点的XY值相等时输出，本题也不例外。难点在于，镜子的状态如何处理。注意到镜子的数目<10，每一镜子仅有两种状态 \ 和/ 。因此将每一面镜子左右视为0与1，得到二进制编码的值hash，存入BFS中的节点。最大节点状态为2^10*10*10=102400 ，时间和空间上完全满足要求。这里总共有三个102400的数组。一个队列Q，一个step存放某节点的步数，一个sight进行预处理，记录下当镜子出于某种状态hash下，每个点是否能够访问。代码太长，格式放不上来，辛辛苦苦打了半天没了，只好帖原文。里面有一些相当有用的技巧，比如对于每一面镜子i的开关操作（0置为1，1置为0）是2^i xor hash，又比如对方向的处理数组与处理函数——这就和马路边的城管一样，常见，而且实用。但是方向函数看代码是看不懂的，需要自己分析一下。 #include #include char a[11][11];int N, M, num_m, num_b, step[10][10][1024], sight[10][10][1024], ans;int dir[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { - 1, 0 }};int p[11] ={ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}; typedef struct{ int x, y, dir, step, h;} Bat;Bat sb, eb, Mirror[12], Q[102410], B[100]; int init ();void bfs ();void proc ( int );int redir ( int, int, int ); //计算方向void print (); int main (){ //freopen ( "in.txt", "r", stdin ); while ( init () ) { bfs ();

Zoj 2281 Way to Freedom

stcrux — 2008-02-11 15:23:00

无向图中给定单源，求到某点路径中最小权边的最大值。可以将其看成求单源最短路径的变种，使用dijkstra算法+最大堆。单源最短路径的算法是：记录从源点出发访问每一点i的最短路为value[i]，对于当前所有value中的最小值点u，进行BFS式的操作，对于每条Edge(u,v)，如果edge(u,v)+value[u] < value[v] 则更新v。这是一个贪心的算法，可以证明每次出队列的u最优。本题求的是最大单边，对此稍做修改。记录每条边目前能承受的最大重量为value[i]（即从源点所遍历路径的最小权中的最大值）。设u是当前结点，对于每条Edge(u,v)，当路径扩展到v时的最小value（min(edge, value[u])）——即路径的最短边——大于value[v] 时更新。在联通图内，每一次要求的路径都是最大，因此在BFS的过程中，边是从大到小排列，对于当前所有value中的最大值点u进行操作。因为点的数目巨大，遍历需要N<100000，可以用堆存放value。实际程序里堆存放的是点的index，使用一个辅助数组来存放index在heap中的位置，如heap[1] = 6, idx[6] = 1。为了编程方便，heap以1开始。由于边数目巨大(M<1000000)，因此使用链表储存。使用num数组保存起点为i的起始位置，next数组保存链表。num[i]=a,next[a]=b,next[b]=c,next[c]=d,next[d]=0，这里abcd都为边数组中的位置，表示以i为起点的边终点为abcd。 1#include 2#include 3 4#define min(x, y) ( x < y ? x : y ) 5#define INF 2000000001 6 7int N, M, src, dst

Zoj 2278 Fight for Food

stcrux — 2008-02-11 14:50:00

2745991 2008-02-07 15:05:00 Accepted 2278 C++ 00:00.68 1708K C.D. 感谢W111（WCY）同学的解题报告。相当出色的DP优化题。类似于最大不下降子序列，一般有O(N2)的简单算法。但N>30000，故需要优化。原先的算法中，设F(i)= 到第i只老鼠时捕捉到的最大数目，F(i)= max(F(j)+1)，j从1到i-1，假如在时限内能从第i到第j只老鼠出现的方格。这里可以预先使用BFS，用time[rati.i][rati.j][ratj.i][ratj.j]来记录从i到j的最小时间，并加以判断。为了优化时间，首先进行预处理，把不可能捕捉到的老鼠删除，把从每一点访问所有点至少需要的时间maxtime[rati.i][rati.j]记录下来。然后把老鼠出现的时间排序。当j从1到i-1访问的时候，可以看到有一些老鼠和当前i的时间相差太多，必然可以访问。这样只要把这些老鼠的最大值+1即可。这些老鼠是：设老鼠j到老鼠i的时间大于i访问所有点的最大时间maxtime。那么，对于k#include #include using namespace std;#define check(x, y) (x >= 0 && y >= 0 &

Poj 3264 Balanced Lineup

stcrux — 2008-02-01 14:31:00

最小白的RMQ，求第i到第j的最大值和最小值差值。采用SparseTable算法，其实就是一种相当高效的打表，空间范围nlogn，每次查询的时间只需要常数。假如是一般的打表，对每组i和j，记录下第i到第j的最大值和最小值，需要的空间为N2，N增大时显然无法满足要求。因此考虑改进算法，适当扩大时间，缩小空间，使之平衡。 ST采用的方法相当高效，二分划分，把每个i的所辖范围划分成1，2，4，8，16的小块，和操作系统中伙伴系统的划分倒有几分类似。以最大值为例。F(i,j)表示以i位元素开始，连续2i个元素中的最大值。初值设所有的F(i,0)即为i的值。那么，F[i,j]=max（F[i，j-1],F[i+2^(j-1)，j-1]）。这个等式不难推出。然后计算l和r区间最大值时，只要划分成两块小且互相覆盖的区间就可以了。第一次做的时候计算最后区间出了点差错，百思不得其解。为什么是(ln(r-l+1)/ln(2))；r-l计算莫非会出精度错误？ #include #include #include int N, Q, a[50000], s[16][50000], t[16][50000], A, B, L; #define max( x, y ) ( (x) > (y) ? (x) : (y) )#define min( x, y ) ( (x) < (y) ? (x) : (y) ) void pt (){ int i, j; for ( i = 0; i <= L; i ++ ) { for ( j = 0; j < N; j ++ ) { printf ( "%d ", t[i][j] ); &n

Zoj 1542 Network

stcrux — 2008-01-23 13:28:00

2730750 2008-01-23 13:12:47 Accepted 1542 C++ 00:00.24 728K C.D. 求最大边最短的生成树。我怀疑即为最小生成树【？】。因为假如按照Prim算法，每次求得的都为一个集合到另一个集合的最短边，也就是不可能生成两棵树，一颗三条边为2，2，2，一颗为1，1，3；这样的情况应该会产生1，1，2 的生成树。【未严格证明】但是在求最大边的时候，显然是用排序+并查集更易得到结果。值得注意的是几点。 1.在unionset操作里使用了不同的返回值分辨不同的处理情况。 2.qsort的处理。 /* zoj 1542 author: Crux.D date: 2008.1.23 description: mst, kruscal, n-1 edge*/ #include #include #include typedef struct{ int t1, t2, l;} Con; Con hub[15000], ans[1001];int N, M, ans_num, max_len; // hub个数，connection数量，生成树边数（N-1），最大边长度 int cmp ( const void *a, const void *b ){ Con *A = ( Con* ) a; Con *B = ( Con* ) b; if ( A->l == B->l ) { if ( A->t1 == B->t1 ) return A->t2 > B->t2; return A->t1 > B->t1; } return A->l > B->l;} void pt (){ int i; for ( i = 0;

Zoj 2833 Friendship

stcrux — 2008-01-22 18:40:00

2730205 2008-01-22 18:15:30 Accepted 2833 C++ 00:00.95 1180K C.D. 这大概就是所谓的RPWT，拿出来炫耀一下。【灰溜溜爬开】其实这题的时限是3000ms，还宽裕的很。但前十名都能把时间压到500ms以内，说明普通的并查集还有值得优化的地方。顺便讲一句，这题通过的人数好X多。第一次写的时候根本就忘了什么是压缩路径，可耻地TLE鸟。【= =】发现上一次写并查集是一年前的事情，结果又忘记怎么做了……【为什么是又】所谓的并查集，也只不过是一枚特殊的树罢了。这棵树在完成findset操作之后，高度至多为2，而且形式为根节点下面N个叶子——这就是压缩；在完成两棵树的合并之后高度至多为3.为了方便编写，采用的是数组而不是链表；这一点我倒是牢牢记住了。 /* zoj 2833 author : Crux.D date : 2008.1.21 description : unionset*/ #include #include int parent[100001], num[100001], N, M, cs = 0; void init (){ int i; for ( i = 0; i <= N; i ++ ) { parent[i] = -1; num[i] = 1; } if ( cs ++ ) printf ( "\n" ); printf ( "Case %d:\n", cs );} int find_set ( int n ){ //寻找树的根节点 int pre = n; while ( parent[pre] != -1 ) { pre = parent[pre]; } int root = pre; //非递归从底到顶压缩路径，简化为高度为2的树 while ( n != root ) { &

终于考完了

stcrux — 2008-01-20 21:59:00

借用史达林的一句话，考一次研（失败）是场悲剧，多考几次就是统计。几天不上zoj的主页，惊奇地发现主页改版了，改的就和我们学校一摸一样。Ranklist上一群牛人，实在是望尘莫及。这样下去，早晚有一天zoj的题目会被他们做完。

南哥的房子

stcrux — 2007-05-28 22:20:00

注：仅以此文纪念我的大学四年，和有趣的室友们，特别是LC，此文来源于他的idea。本文风格受到了王小波《红拂夜奔》的影响，这是一本有趣的小说，我很喜欢。 —————————————正文的分割线————————————————— 很多年以前，杭州城的天是黑蒙蒙的，云是黑压压的，空气是黑黝黝的，整个城市是黑漆漆的。西域来的黑人在路上行走，谁也看不见，被车轧死的事情时有发生——这是官方说辞，事实上，衙门里的失踪人口册被记得密密麻麻。后来黑人在出门之前先把自己染白，这就是杭州城最早的一批白人。很多年以前，南哥就住在这座城市里。很多年以前，南哥在这座城市里租着一间房子。在这座城市，房价很高，很多人都住不起。但就像你所知的，世界上有穷人，自然也有富人。有些富人雇了马车，把成堆成堆的钱运进城来，成批成批的马因此而累死。但是他们惊异地发现，即便用上再好的神驹，马车的速度永远比不上房价飞涨的速度。有人曾经用钱堆满了一座别墅，却发现这点钱只买的起一间茅房。孔子曰，逝者如斯夫，不舍昼夜。他老人家掐着钟点周游列国，还不是为了买房！只可惜有钱人少，没钱人多，所以很多人选择了租房。南哥是未来的中行行长，未来的联合国秘书长，未来的银河系领导，但是此时他没有钱。和所有的没钱人一样，他在离工作的地方不远处租了一间房子。一般而言，租房有合租的，有单租的，有两室一厅的，有一室一厅的，有20平米的，有40平米的。南哥找的是2平米，二楼，一个房间的。也有3平米的，南哥说，根本没必要，床够放了。其实我看原因还是为了省钱。一个平方月租50两银子，一年就要多交600两银子。不管房价是涨是跌，银子总是重要的，哪朝哪代都一样。搬家的那一天，为了把床挪进门，南哥费了很大的心思。这里不得不提一下南哥的床，因为这是人类工程学上的奇迹。南哥的床两米长一米宽，和房间的几何特性刚好吻合；上面睡人，掀开床板以后，下面是暗道直通衣柜。暗道里有梯子，方便爬上爬下。床尾有翻板，翻起来是电脑桌，放下去可以做硬木枕，健脑醒目——但是南哥翻起来以后就再也没放下去过：众所周知，南哥是官府银行（那时叫钱

Zju 1800 Decorations

stcrux — 2007-04-30 22:53:00

最近经常性地在关键时刻掉链子。古希腊先哲说，人不会两次跌进同一个坑——确实，我跌进了两个坑，摔的鼻青脸肿。先是在杭电邀请赛上看错范围，把辅助数组开小，幸好同伴火眼金睛；这道题犯的错误几乎一摸一样，一个a[601][101]的数组开成了a[101][601]。最可恨的是这样的错误假如没有意识到，一辈子都找不出来！ZOJ上wrong answer映的我发绿，莫名其妙，怎么也该打出一个RunTimeError吧……结果我的程序几乎被改成BusyCai同学的程序了…… 这类词典型的dp题目倒也差不多，a[i][k]代表了第k个词语在填入第i个位置时的可能总数。只要扫描上一个位置的所有M词语a[i- 1][j]，满足情况者加入a[i][k]即可。BusyCai的写法比较好，用每个位置a[i][k]去加到下一个位置a[i + 1][j]。a[i][k]可能为0，节省了很多时间。 #include #include int N, L, M, len, a[110][610];char str[610][11]; void init (){ int i; for ( i = 0; i < M; i ++ ) { scanf ( "%s", str[i] ); } memset ( a, 0, sizeof ( a ) ); len = strlen ( str[0] );} int check ( int a, int b ){ int i; for ( i = 1; i < len; i ++ ) { if ( str[a][i] != str[b][i - 1] ) return 0; } return 1;} void dp (){ int i, k, j; for ( k = 0; k < M; k ++ ) { a[len][k] = 1; } for (

USACO Section 1.4 The Clocks

stcrux — 2007-04-10 21:58:00

老实的说，这该称之为穷举——但搜索不也是把所有可能的情况列出来么？无非用的方法巧妙一点……额，是巧妙的多罢了。传说中有位俊朗的数学家王子，为了得到邻国数学家公主的一片芳心，发动全国之力，每个人验证一个数是否为质数，从而得到了一个相当大的质数，为古巴比伦数学的蓬勃发展作出了不可磨灭的贡献。——这就是穷举。BTW，他的想法和并行计算机如出一辙，也不知道谁从谁哪里得到的灵感。但是我听说，两个数学家走到一起，下场都是很悲惨的，不是女孩把拖鞋下到锅里就是男孩饿死。但似乎王子和公主们不用担心这些…… 扯远了。这道题本来想写华丽的bfs……但是写的太华丽了，调试到最后连自己都不知道在写什么。题意是这样的，有9个时钟（A到I），每个时钟只有4档可以拨，12点，3点，6点，9点。有9种操作，每种操作把其中的某几个时钟顺时针拨一档。 Move Affected clocks 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI 那么，给出一个时钟的排列法，如 9 9 126 6 66 3 6 求，最小需要几步，把所有时钟都挑到12点？这是一个非常好的bfs和dfs练习题，但是也相当的难写。在看了某牛人的dfs代码之后，我发现自己比看过之前懂的更少。胡Core也教导我们，要以艰苦朴素为荣。综上所述，我采用了穷举的方法。但是这也是有前提的。第一，每一个时钟都只有四种状态。换句话说，每种操作也是四种状态，进行0，1，2，3次。第二，4的9次方不大…… /*ID: Crux.DPROG: clocksLANG: C++*/ #include #include #include const int L = 10000; FILE * fin = fopen ( "clocks.in", "r" );FILE * fout = fopen ( "clocks.out", "w" ); int x[9]; int c[9][9] = {{ 1, 1, 0, 1, 1, 0, 0, 0, 0

Zju 1586 QS Network

stcrux — 2007-03-27 14:53:00

这题显然还是用prim，经过优化后的prim效率可以达到O(n2)。离省赛越来越近，我也越来越没有状态，这种小白题从昨天晚上开始做，做到断网；今天爬起来继续做，才发现是把a[i][k]赋值无限大的条件写错了——无良的出题者居然加入了两个端点间距离可能为0的情况...... #include #include int a[1010][1010], s[1010], dis[1010], t, n; void pd (){ int i; for ( i = 0; i < n; i ++ ) { printf ( "%d ", dis[i] ); } printf ( "\n" );} void init (){ int i, k; scanf ( "%d", &n ); for ( i = 0; i < n; i ++ ) { scanf ( "%d", &s[i] ); } for ( i = 0; i < n; i ++ ) { for ( k = 0; k < n; k ++ ) { scanf ( "%d", &a[i][k] ); &nb

搜索和动态规划的一些简单分析

stcrux — 2007-03-14 19:12:00

tieren同学提问，“深搜和动态规划有什么区别与联系呢”，留言板上写不下，把题目扩充一下，写到这里来。在我看来，广搜和动态规划更像些：两者都是从上往下计算，在程序中都可以从前到后分出很明显的层次。广搜采用的是队列，后进前出，队列中每一个元素需要记录下他的层次；而动归中一个状态就是一个层次。而深搜是先按第一种算法（如，搜索第一个元素）从第一层计算到最后一层，（一般而言是算那些是否有解的问题），如果发现无解倒退一层，换第二种算法（搜第二个）……依次类推。比如在棋盘上跳马，每一步就是一个层次。在广搜中可以记录下每一步的行号列号和步数，然后推出这个记录，把它的下一步（n种情况）推入队列中。在动态规划里，扫描所有格子，跳马，在每个跳到的格子里记录下跳到该格需要的步数，这样就算一步（一个层次）。所以从记录的时间效率来看，如果棋盘足够大，显然是广度搜索合算。因为在动归里，每一步都有很多无用的格子，不记录任何东西。但是动归在棋盘足够大，步数足够多时也节约了很多空间，因为它的空间恒定为棋盘大小，而广搜则把同一个格子记录了好多遍，还附带记录了它的行号列号——前提是不做任何优化。至于另外一种搜索——深搜，可以这样说，在那些求“是否有解”的问题中，深搜和动态规划都很有用。比如求用面值为A元，B元，C元的三种纸币能否凑出SUM元钱之类的问题。深搜处理是写一个递归，然后按某种顺序一直累加到底，若无解则回溯。动归的话可以开一个SUM的数组，初始时凑到0元。然后每一次扫描整个数组，在凑到的钱数上分别加上三种纸币，直到结束。当然也可以用广搜来做，同样是以0元为第一步，然后开始累加，这简直就是动态规划的变种了，但是同样可能会有重复记录。那么还有一个问题，深搜和动归的效率谁优谁劣？这不是一个简单的问题。因为深搜实际上是一个二进制的问题，对于每个元素有两种选择：搜与不搜。所以如果给定N种纸币，为了简便起见，在每种纸币只许用一次的情况下，要想把所有情况遍历一遍，O(N)=2N。（因为深搜事实上得到的是一个组合，总共有2N个组合）我们也知道，二进制是一种很奇妙的东西，当N=20时只有1M，N=30时就是1

【ZZ】关于typedef struct

stcrux — 2007-03-13 22:34:00

1. 基本解释　　typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。这里的数据类型包括内部数据类型（int,char等）和自定义的数据类型（struct等）。　　在编程中使用typedef目的一般有两个，一个是给变量一个易记且意义明确的新名字，另一个是简化一些比较复杂的类型声明。　　至于typedef有什么微妙之处，请你接着看下面对几个问题的具体阐述。　　2. typedef & 结构的问题　　当用下面的代码定义一个结构时，编译器报了一个错误，为什么呢？莫非C语言不允许在结构中包含指向它自己的指针吗？请你先猜想一下，然后看下文说明： typedef struct tagNode{　char *pItem;　pNode pNext;} *pNode; 　　答案与分析：　　1、typedef的最简单使用 typedef long byte_4; 　　给已知数据类型long起个新名字，叫byte_4。　　2、 typedef与结构结合使用 typedef struct tagMyStruct{ 　int iNum;　long lLength;} MyStruct; 　　这语句实际上完成两个操作：　　1) 定义一个新的结构类型 struct tagMyStruct{ 　int iNum; 　long lLength; }; 　　分析：tagMyStruct称为“tag”，即“标签”，实际上是一个临时名字，struct 关键字和tagMyStruct一起，构成了这个结构类型，不论是否有typedef，这个结构都存在。　　我们可以用struct tagMyStruct varName来定义变量，但要注意，使用tagMyStruct varName来定义变量是不对的，因为struct 和tagMyStruct合在一起才能表示一个结构类型。