1
#include<iostream>
2using namespace std;
3#define MAX 5000
4
5char str[MAX+2];
6char re_str[MAX+2];
7//int res[MAX+1][MAX+1]; //MLE
8int res[2][MAX+1];
9int n;
10
11void dp()
12
{
13
int i,j;
14 for(j=0;j<=n;j++)
15 res[0][j]=j;
16 res[1][0]=1;
17 for(i=1;i<=n;i++)
18
{
19 res[i%2][0]=i;
20 for(j=1;j<=n;j++)
21 {
22 if(str[i]==re_str[j])
23 res[i%2][j]=res[(i-1)%2][j-1];
24 else{
25 res[i%2][j]=min(res[(i-1)%2][j],res[i%2][j-1])+1;
26
}
27 }
28 }
29
}
30int main()
31{
32 int i;
33 scanf("%d",&n);
34 for(i=1;i<=n;i++)
35 {
36 scanf(" %c",&str[i]);
37 re_str[n-i+1]=str[i];
38 }
39 dp();
40 printf("%d\n",res[n%2][n]>>1);
41 return 0;
42}
//
posted @
2009-05-10 14:38 wyiu 阅读(195) |
评论 (0) |
编辑 收藏
第一题完全靠自己的DP，一遍AC
高兴...
1#include<iostream>
2using namespace std;
3#define MAX 100
4
5int table['T'+1]['T'+1]; //scoring matrix
6int score[MAX+1][MAX+1]; //score[i][j]表示a串有i个基，b串j个基的最大score
7char a[MAX+1]; //string a
8char b[MAX+1]; //string b
9int la; //length of a
10int lb; //length of b
11
12void init()
13{
14 table['A']['A']=5;
15 table['A']['C']=-1;
16 table['A']['G']=-2;
17 table['A']['T']=-1;
18 table['A']['-']=-3;
19
20 table['C']['A']=-1;
21 table['C']['C']=5;
22 table['C']['G']=-3;
23 table['C']['T']=-2;
24 table['C']['-']=-4;
25
26 table['G']['A']=-2;
27 table['G']['C']=-3;
28 table['G']['G']=5;
29 table['G']['T']=-2;
30 table['G']['-']=-2
31 ;
32 table['T']['A']=-1;
33 table['T']['C']=-2;
34 table['T']['G']=-2;
35 table['T']['T']=5;
36 table['T']['-']=-1;
37
38 table['-']['A']=-3;
39 table['-']['C']=-4;
40 table['-']['G']=-2;
41 table['-']['T']=-1;
42}
43void dp()
44{
45 int i,j;
46 score[0][0]=0;
47 for(i=1;i<=la;i++)
48 score[i][0]=score[i-1][0]+table[a[i]]['-'];
49 for(i=1;i<=lb;i++)
50 score[0][i]=score[0][i-1]+table['-'][b[i]];
51 for(i=1;i<=la;i++)
52 for(j=1;j<=lb;j++)
53 score[i][j]=max(score[i-1][j-1]+table[a[i]][b[j]],max(score[i][j-1]+table['-'][b[j]],score[i-1][j]+table[a[i]]['-']));
54}
55
56
57int main()
58{
59 int T;
60 scanf("%d",&T);
61 init();
62 while(T--)
63 {
64 memset(a,0,sizeof(a));
65 memset(b,0,sizeof(b));
66 scanf("%d",&la);
67 scanf("%s",a+1);
68 scanf("%d",&lb);
69 scanf("%s",b+1);
70 dp();
71 printf("%d\n",score[la][lb]);
72 }
73 return 0;
74}
75
posted @
2009-05-02 16:21 wyiu 阅读(218) |
评论 (0) |
编辑 收藏
//将第i行到第j行的每列求和，保存于csum，然后求最大字串和
1#include<iostream>
2using namespace std;
3#define MAXN 100
4#define _INF -10000000
5
6int a[MAXN+1][MAXN+1];
7int csum[MAXN+1];
8
9int maxSubArray(int csum[],int n)
10{
11 int b=0,max=_INF,j;
12 for(j=1;j<=n;j++)
13 {
14 if(b>0) b+=csum[j];
15 else b=csum[j];
16 if(b>max) max=b;
17 }
18 return max;
19 }
20
21int main()
22{
23 int n,i,j,k,t,res=_INF;
24 scanf("%d",&n);
25 for(i=1;i<=n;i++)
26 for(j=1;j<=n;j++)
27 scanf("%d",&a[i][j]);
28
29 for(i=1;i<=n;i++)
30 {
31 memset(csum,0,sizeof(csum));
32 for(j=i;j<=n;j++)
33 {
34 for(k=1;k<=n;k++)
35 csum[k]+=a[j][k];
36 t=maxSubArray(csum,n);
37 if(t>res) res=t;
38 }
39 }
40 printf("%d\n",res);
41 return 0;
42}
43
posted @
2009-05-02 13:58 wyiu 阅读(107) |
评论 (0) |
编辑 收藏
一遍SPFA求去的最短路径，把图的边逆向，再一遍SPFA，求出回来的最短路径...
SPFA其实是Bellman-Ford使用队列的优化
1#include<iostream>
2#include<queue>
3using namespace std;
4#define INF 2147483647 //2,147,483,647
5#define MAXP 1000000 //1,000,000
6#define MAXSUM 1000000000 //1,000,000,000
7
8struct Edge
9{
10 //int src;
11 int vertex;
12 int weight;
13 Edge *next;
14};
15
16Edge edge[MAXP*2+1];
17Edge *go[MAXP+1];
18Edge *back[MAXP+1];
19int dis[MAXP+1];
20bool flag[MAXP+1]; //false denote that the vertex is not in the queue
21
22void creatlist(int vn,int en)
23{
24 int s,d,w,i,j;
25 for(i=1;i<=vn;i++)
26 {
27 go[i]=NULL;
28 back[i]=NULL;
29 flag[i]=false;
30 }
31 for(i=1,j=1;i<=en;i++)
32 {
33 scanf("%d%d%d",&s,&d,&w);
34 edge[j].vertex=d;
35 edge[j].weight=w;
36 edge[j].next=go[s];
37 go[s]=&edge[j++];
38
39 edge[j].vertex=s;
40 edge[j].weight=w;
41 edge[j].next=back[d];
42 back[d]=&edge[j++];
43 }
44}
45
46void spfa(Edge *adjlist[],int vn,int src)
47{
48 int i,u,v,tmp;
49 Edge *p;
50 queue<int> Queue;
51 for(i=1;i<=vn;i++)
52 dis[i]=INF;
53 dis[src]=0;
54 Queue.push(src);
55 while(!Queue.empty())
56 {
57 u=Queue.front();
58 Queue.pop();
59 flag[u]=false;
60 p=adjlist[u];
61 while(p!=NULL)
62 {
63 tmp=dis[u]+p->weight;
64
65 v=p->vertex;
66 if(dis[v] > tmp)
67 {
68 dis[v]=tmp;
69 if(flag[v]==false)
70 {
71 Queue.push(v);
72 flag[v]=true;
73 }
74 }
75 /**//*
76 if(dis[p->vertex] > tmp)
77 {
78 dis[p->vertex]=tmp;
79 if(flag[p->vertex]==false)
80 {
81 Queue.push(p->vertex);
82 flag[p->vertex]=true;
83 }
84 }*/
85 p=p->next;
86 }
87 }
88}
89
90int main()
91{
92 int n,p,q,i;
93 __int64 sum;
94 scanf("%d",&n);
95 while(n--)
96 {
97 scanf("%d%d",&p,&q);
98 creatlist(p,q);
99 sum=0;
100 spfa(go,p,1);
101 for(i=1;i<=p;i++)
102 sum+=dis[i];
103 spfa(back,p,1);
104 for(i=1;i<=p;i++)
105 sum+=dis[i];
106 printf("%I64d\n",sum);
107 }
108 return 0;
109}
posted @
2009-04-27 01:31 wyiu 阅读(134) |
评论 (0) |
编辑 收藏
above[i]记录i方块之上的方块数
rank[i]记录树上总节点数(根节点)
M x y时把y所在树加到x所在树后，原x所在树的节点的above大小得更新，由于有路经压缩...具体看程序吧
1#include<iostream>
2using namespace std;
3#define MAXN 30000
4#define MAXP 100000
5
6int parent[MAXN+1];
7int rank[MAXN+1]; //该数的结点(方块)数
8int above[MAXN+1]; //记录该方块之上有的方块数
9
10void init(int n=MAXN)
11{
12 int i=0;
13 for(i=1;i<=n;i++)
14 {
15 parent[i]=-1;
16 rank[i]=1;
17 }
18}
19
20int find(int x)
21{
22 int p = x,temp,tp;
23 while( parent[p] > 0) p = parent[p];
24 while( x != p )
25 {
26 tp=temp = parent[x];
27 parent[x] = p;
28 while(temp!= p) //难理解的地方
29 {
30 above[x]+=above[temp];
31 temp=parent[temp];
32 }
33 x = tp;
34 }
35 return p;
36}
37
38void Union(int x,int y)
39{
40 int root1=find(x),
41 root2=find(y);
42 if(root1==root2) return ;
43 above[root2]=rank[root1];
44 rank[root1]+=rank[root2];
45 parent[root2]=root1;
46}
47
48int main()
49{
50 int P,x,y;
51 char c;
52 init();
53 scanf("%d",&P);
54 while(P--)
55 {
56 scanf(" %c",&c,&x,&y);
57 if(c=='M')
58 {
59 scanf("%d%d",&x,&y);
60 Union(x,y);
61 }else{
62 scanf("%d",&x);
63 y=find(x);
64 printf("%d\n",rank[y]-above[x]-1);
65 }
66 }
67 return 0;
68}
69
70
71
72
posted @
2009-04-23 20:57 wyiu 阅读(182) |
评论 (0) |
编辑 收藏 1#include<iostream>
2using namespace std;
3#define MAXN 50000
4
5int parent[MAXN+1];
6
7void init(int n)
8{
9 int i;
10 for(i=1;i<=n;i++)
11 parent[i]=-1;
12}
13
14
15int find(int x)
16{
17 if(parent[x]<0)
18 return x;
19 else return parent[x]=find(parent[x]);
20
21}
22
23void Union(int x,int y)
24{
25 int root1=find(x),
26 root2=find(y);
27 if(root1==root2) return;
28 if(parent[root1]<parent[root2])
29 {
30 parent[root1]+=parent[root2];
31 parent[root2]=root1;
32 }else{
33 parent[root2]+=parent[root1];
34 parent[root1]=root2;
35 }
36}
37
38
39int main()
40{
41 int n,m,x,y,i,k=1,sum;
42 memset(parent,-1,sizeof(parent));
43 while( scanf("%d%d",&n,&m)==2 && n!=0 )
44 {
45 sum=0;
46 while(m--)
47 {
48 scanf("%d%d",&x,&y);
49 Union(x,y);
50 }
51 for(i=1;i<=n;i++)
52 {
53 if(parent[i]<0)
54 sum++;
55 parent[i]=-1;
56 }
57 printf("Case %d: %d\n",k++,sum);
58 }
59 return 0;
60}
posted @
2009-04-22 20:20 wyiu 阅读(83) |
评论 (0) |
编辑 收藏 1#include<iostream>
2using namespace std;
3#define MAXN 30000
4#define MAXM 500
5
6int parent[MAXN];
7
8void init(int n=MAXN)
9{
10 int i;
11 for(i=0;i<n;i++)
12 parent[i]=-1;
13}
14int find(int x)
15{
16 if(parent[x]<0)
17 return x;
18 else return parent[x]=find(parent[x]);
19}
20
21int Union(int x,int y)
22{
23 int root1=find(x),
24 root2=find(y);
25 if(root1==root2) return root1;
26 if(parent[root1]<parent[root2])
27 {
28 parent[root1]+=parent[root2];
29 parent[root2]=root1;
30 return root1;
31 }else{
32 parent[root2]+=parent[root1];
33 parent[root1]=root2;
34 return root2;
35 }
36}
37int main()
38{
39 int n,m,i,j,k,x,root;
40 while( scanf("%d%d",&n,&m)==2 && n!=0 )
41 {
42 init(n);
43 for(i=0;i<m;i++)
44 {
45 scanf("%d",&k);
46 for(j=1;j<=k;j++)
47 {
48 scanf("%d",&x);
49 if(j==1) root=x;
50 root=Union(root,x);
51 }
52 }
53 printf("%d\n",-parent[find(0)]);
54 }
55 return 0;
56}
posted @
2009-04-22 20:16 wyiu 阅读(194) |
评论 (0) |
编辑 收藏 1#include<iostream>
2using namespace std;
3#define MAXN 2000
4#define string1 "Scenario #"
5#define string2 "Suspicious bugs found!"
6#define string3 "No suspicious bugs found!"
7
8int parent[MAXN+1];
9int rank[MAXN+1];
10int dif[MAXN+1];
11
12void Init(int n=MAXN)
13{
14 int i;
15 for(i=0;i<=n;i++)
16 {
17 rank[i]=0;
18 parent[i]=i;
19 dif[i]=-1;
20 }
21}
22
23int find(int x)
24{
25
26 if(parent[x]!=x)
27 parent[x]=find(parent[x]);
28 return parent[x];
29}
30
31int merge_set(int a,int b)
32{
33 if(a==-1) return b;
34 if(b==-1) return a;
35 if(rank[a]>rank[b])
36 {
37 parent[b]=a;
38 return a;
39 }else{
40 parent[a]=b;
41 if(rank[a]==rank[b])
42 rank[b]++;
43 return b;
44 }
45}
46void Union(int a,int b)
47{
48 int root1=find(a),
49 root2=find(b),
50 da=merge_set(dif[root1],root2), //b的新根
51 db=merge_set(root1,dif[root2]); //a的新根
52 dif[db]=da;
53 dif[da]=db;
54}
55
56
57int main()
58{
59 int S,N,M,a,b,i;
60 bool flag;
61
62 scanf("%d",&S);
63 for(i=1;i<=S;i++)
64 {
65 scanf("%d%d",&N,&M);
66 Init(N);
67 flag=true;
68 while(M--)
69 {
70 scanf("%d%d",&a,&b);
71 Union(a,b);
72 if(find(a)==find(b)) flag=false;
73 }
74 if(flag==false)
75 printf("%s%d:\n%s\n\n",string1,i,string2);
76 else printf("%s%d:\n%s\n\n",string1,i,string3);
77
78 }
79 return 0;
80}
81
posted @
2009-04-21 16:42 wyiu 阅读(158) |
评论 (0) |
编辑 收藏 1#include<iostream>
2using namespace std;
3#define MAXN 100000
4#define string1 "Not sure yet."
5#define string2 "In different gangs."
6#define string3 "In the same gang."
7
8int parent[MAXN+1];
9int rank[MAXN+1];
10int dif[MAXN+1];
11
12void Init(int n=MAXN)
13{
14 int i;
15 for(i=0;i<=n;i++)
16 {
17 rank[i]=0;
18 parent[i]=i;
19 dif[i]=-1;
20 }
21}
22
23int find(int x)
24{
25
26 if(parent[x]!=x)
27 parent[x]=find(parent[x]);
28 return parent[x];
29}
30
31int merge_set(int a,int b)
32{
33 if(a==-1) return b;
34 if(b==-1) return a;
35 if(rank[a]>rank[b])
36 {
37 parent[b]=a;
38 return a;
39 }else{
40 parent[a]=b;
41 if(rank[a]==rank[b])
42 rank[b]++;
43 return b;
44 }
45}
46void Union(int a,int b)
47{
48 int root1=find(a),
49 root2=find(b),
50 da=merge_set(dif[root1],root2), //b的新根
51 db=merge_set(root1,dif[root2]); //a的新根
52 dif[db]=da;
53 dif[da]=db;
54}
55
56int main()
57{
58 int T,N,M,a,b,i;
59 char c;
60 scanf("%d",&T);
61 while(T--)
62 {
63 //memset(parent,0,sizeof(parent));
64 scanf("%d%d",&N,&M);
65 Init(N);
66 while(M--)
67 {
68 scanf(" %c%d%d",&c,&a,&b);
69 if(c=='A')
70 {
71 a=find(a);
72 b=find(b);
73 if(a==b)
74 printf("%s\n",string3);
75 else {
76 if(a==dif[b])
77 printf("%s\n",string2);
78 else printf("%s\n",string1);
79 }
80 }
81 else
82 {
83 Union(a,b);
84 }
85 }
86
87 }
88 return 0;
89}
90
posted @
2009-04-21 16:36 wyiu 阅读(147) |
评论 (0) |
编辑 收藏union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数、最小公共祖先、带限制的作业排序，还有最完美的应用：实现Kruskar算法求最小生成树。其实，这一部分《算法导论》讲的很精炼。
一般采取树形结构来存储并查集，在合并操作时可以利用树的节点数(加权规则)或者利用一个rank数组来存储集合的深度下界--启发式函数，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M Alpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是线性的。
它支持以下三种操作:
－Union (Root1, Root2) //合并操作；把子集合Root2和子集合Root1合并.要求：Root1和 Root2互不相交,否则不执行操作.
－Find (x) //搜索操作；搜索元素x所在的集合,并返回该集合的名字--根节点.
－UFSets (s) //构造函数。将并查集中s个元素初始化为s个只有一个单元素的子集合.
－对于并查集来说，每个集合用一棵树表示。
－集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。
－为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。
以下给出我的两种实现:
1//Abstract: UFSet
2
3//Author:Lifeng Wang （Fandywang）
4
5
6
7
8// Model One 与Model 2 路径压缩方式不同,合并标准不同
9
10const int MAXSIZE = 500010;
11
12int rank[MAXSIZE]; // 节点高度的上界
13
14int parent[MAXSIZE]; // 根节点
15
16int FindSet(int x){// 查找+递归的路径压缩
17
18 if( x != parent[x] ) parent[x] = FindSet(parent[x]);
19
20 return parent[x];
21
22}
23
24void Union(int root1, int root2){
25
26 int x = FindSet(root1), y = FindSet(root2);
27
28 if( x == y ) return ;
29
30 if( rank[x] > rank[y] ) parent[y] = x;
31
32 else{
33
34 parent[x] = y;
35
36 if( rank[x] == rank[y] ) ++rank[y];
37
38 }
39
40}
41
42void Initi(void){
43
44 memset(rank, 0, sizeof(rank));
45
46 for( int i=0; i < MAXSIZE; ++i ) parent[i] = i;
47
48}
49
50
51
52
53// Model Two
54
55const int MAXSIZE = 30001;
56
57int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目;
58
59 //非根节点j,pre[j] = k,其中k是j的父节点
60
61int Find(int x){//查找+非递归的路径压缩
62
63 int p = x;
64
65 while( pre[p] > 0 ) p = pre[p];
66
67 while( x != p ){
68
69 int temp = pre[x]; pre[x] = p; x = temp;
70
71 }
72
73 return x;
74
75}
76
77void Union(int r1, int r2){
78
79 int a = Find(r1); int b = Find(r2);
80
81 if( a == b ) return ;
82
83 //加权规则合并
84
85 if( pre[a] < pre[b] ){
86
87 pre[a] += pre[b]; pre[b] = a;
88
89 }
90
91 else {
92
93 pre[b] += pre[a]; pre[a] = b;
94
95 }
96
97}
98
99void Initi(void)
100
101{
102
103 for( int i=0; i < N; ++i ) pre[i] = -1;
104
105}
106
107
并查集的一些题目和我的相关解题报告:
POJ 1611 The Suspects 最基础的并查集
POJ 2524 Ubiquitous Religions 最基本的并查集
POJ 1182 食物链 并查集的拓展
注意: 只有一组数据;
要充分利用题意所给条件:有三类动物A,B,C，这三类动物的食物链
构成了有趣的环形。A吃B， B吃C，C吃A。也就是说:只有三个group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度优先遍历
每次遍历记录下该点是男还是女，只有:男-〉女，女-〉男满足，否则，找到同性恋，结束程序。
法二:二分图匹配
法三:并查集的拓展:和1182很像，只不过这里就有两组，而1182是三组,1611无限制
POJ 1861 Network == zju_1542 并查集+自定义排序+贪心求"最小生成树"
答案不唯一，不过在ZOJ上用QSORT()和SORT()都能过，在POJ上只有SORT()才能过...
POJ 1703 Find them, Catch them 并查集的拓展
这个和POJ 2492 A Bug's Life很像，就是把代码稍微修改了一下就AC了！
注意：And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是说只有两个组。
POJ 2236 Wireless Network 并查集的应用
需要注意的地方：1、并查集；2、N的范围，可以等于1001；3、从N+1行开始，第一个输入的可以是字符串。
POJ 1988 Cube Stacking 并查集很好的应用
1、与 银河英雄传说==NOI2002 Galaxy一样；2、增加了一个数组behind[x],记录战舰x在列中的相对位置；3、详细解题报告见银河英雄传说。
JOJ 1905 Freckles == POJ 2560 最小生成树
法一：Prim算法；法二：并查集实现Kruskar算法求最小生成树
JOJ 1966 Super Market III == PKU 1456 Supermarket 带限制的作业排序问题（贪心+并查集）
提高题目：
POJ 2912 Rochambeau
POJ 1733 Parity game
POJ 1308 Is It A Tree?
posted @
2009-04-21 14:56 wyiu 阅读(181) |
评论 (0) |
编辑 收藏