find.h
#ifndef FIND_H
#define FIND_H
template <typename ITER , typename T>
ITER find(ITER begin, ITER end, T value)
{
	ITER it;
	for(it = begin; it != end; ++it)
		if(*it == value)
			break;
	return it;
}
#endif

count.h
#ifndef COUNT_H
#define COUNT_H
template <typename ITER , typename T>
int count(ITER begin, ITER end, T value)
{
	int sum = 0;
	for(ITER it = begin; it != end; ++it)
	{
		if(*it == value)
			++sum;
	}
	return sum;
}
#endif

以后接着写。

#ifndef UFSET_H
#define UFSET_H
class UFset
{
	public:
		UFset(int);
		void Union(int ,int);
		int Find(int);
		int & operator [] (int i){return parent[i];}
		int size(){return length;}
	private:
		int length;//集合的个数
		int * parent;
};
UFset::UFset(int len)
{
	length = len;
	parent = new int [length + 1];
	for(int k = 1; k <= length; k++)
		parent[k] = -1;
}
int UFset::Find(int x)
{
	 int i;
	 for(i = x; parent[i] >= 0; i = parent[i]);//搜索根节点
	 while(i!=x)//路径压缩
	 {
		  int tmp = parent[x];
		  parent[x] = i;
		  x = tmp;
	 }
	 return i;
}
void UFset::Union(int x,int y)//合并
{
	int pX = Find(x);
	int pY = Find(y);
	if(pX != pY)
	{
		int tmp = parent[pX] + parent[pY];
		if(parent[pX] > parent[pY])
		{
			parent[pX] = pY;
			parent[pY] = tmp;
		}
		else 
		{
			parent[pY] = pX;
			parent[pX] = tmp;
		}
		length--;
	}
}
#endif

动态规划即是一个重点，又是一个难点。
今天终于做出了一题像样的动态规划题。
Problem Id:1163  User Id:beyonlin_SCUT
Memory:100K  Time:0MS
Language:C++  Result:Accepted
http://acm.pku.edu.cn/JudgeOnline/problem?id=1163

The Triangle
Time Limit:1000MS  Memory Limit:10000K
Total Submit:3415 Accepted:1988

Description

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5


(Figure 1)

Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output
Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Sample Output
30


分析：
题意简化为：
从第一行开始走到最后一行，每步可以向下走或右下走。
所求即为从第一行走到最后一行经过的数总和的最大值。
令p[][]存储input。
5
7
3 8
8 1 0
2 7 4 4
|     \ |  \
4 5 2 6 5

如上图，令i为行，j为列,
d[i][j]为从第一行走到第i行第j列的最大值。
对于(i,j)这个点，它可以从不同方向走来，如图' | '代表从上方走来，' \ '代表从左上方走来。

则动态规则方程为：
                  {     d[i-1][1]+p[i][1]   (j=1)
d[i][j]=Max{     Max( d[i-1][j-1] , d[i-1][j] ) + p[i][j]   (1<j<i)
                  {     d[i-1][i-1]+p[i][i]   (j=i)

结果为Max(d[n][j]) , (1<=j<=n)

代码如下：

#include<cstdio>
int p[100][100];
int d[100][100];
int Max(int a,int b)
{return a>b?a:b;}
int main()
{
	int i,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		int j;
		for(j=1;j<=i;j++)
			scanf("%d",p[i]+j);
	}
	d[1][1]=p[1][1];
	for(i=2;i<=n;i++)
	{
		int j;
		d[i][1]=d[i-1][1]+p[i][1];
		for(j=2;j<=i;j++)
			d[i][j]=Max(d[i-1][j-1],d[i-1][j])+p[i][j];
		d[i][i]=d[i-1][i-1]+p[i][i];
	}
	int max=0;
	for(i=1;i<=n;i++)
	{
		if(d[n][i]>max)
			max=d[n][i];
	}
	printf("%d\n",max);
	return 0;
}

3 6
HFDFFB
AJHGDH
DGAGEH

6

我的程序：
#include<cstdio>
#include<stack>
using namespace std;
struct node
{
	int row;
	int col;
	int dire;
};
char p[30][30];
char flag[30];
int incr[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main()
{
	int i,row,col;
	scanf("%d%d",&row,&col);
	getchar();
	char ch[30];
	for(i=1;i<=row;i++)
	{
		gets(ch);
		int j;
		for(j=1;j<=col;j++)
			p[i][j]=ch[j-1];
	}
	//初始化，外加一层
	for(i=0;i<=col+1;i++)
	{
		p[0][i]='0';
		p[row+1][i]='0';
	}
	for(i=0;i<=row+1;i++)
	{
		p[i][0]='0';
		p[i][col+1]='0';
	}
	int Maxmove=0;//最大步数
	stack<node>path;
        //栈初始化
	int r=1,c=1,dire=0,f=0,move=1;
	node in;
	in.row=r;
	in.col=c;
	in.dire=dire;
	path.push(in);
	flag[f++]=p[r][c];
	while(!path.empty())
	{
		if(dire<4)
		{
			int r2=r+incr[dire][0];
			int c2=c+incr[dire][1];
			bool b=true;
			for(int k=0;k<f;k++)//搜索是否已访问或路不通
			{
				if(flag[k]==p[r2][c2] || p[r2][c2]=='0')
				{
					dire++;
					b=false;
					break;
				}
			}
			if(b)//路通
			{
				node in;
				in.row=r2;
				in.col=c2;
				in.dire=dire;
				path.push(in);//进栈
				move++;
				flag[f++]=p[r2][c2];//标志已访问
				r=r2;
				c=c2;
				dire=0;
			}
		}
		else//找到一个解
		{
			if(move>Maxmove)
				Maxmove=move;
			move--;
			dire=path.top().dire+1;	//回溯，去除访问标志
			path.pop();
			flag[--f]='\0';
			if(!path.empty())
			{
				r=path.top().row;
				c=path.top().col;
			}
		}
	}
	printf("%d\n",Maxmove);
	return 0;
}

今天在PKU上做了我第一题广度优先搜索题：
Problem Id:2627  User Id:beyonlin_SCUT
Memory:64K  Time:575MS
Language:C++  Result:Accepted
个人认为算法复杂度应该为O(n^2)或更小。不知是不是这样。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2627

Gopher and hawks
Time Limit:1000MS  Memory Limit:65536K
Total Submit:900 Accepted:328

Description
A gopher sits in a hole located at (xs, ys) and wants to get to a hole located at (xt, yt). The gopher can run at a constant speed of v m/sec. However, if the gopher is outside of a hole for more than a m minutes he will become a supper to hawks flying over the holes. Can the gopher make it?

Input
The first line of input contains two positive integer numbers: v -- gopher's speed in meters per second and m -- the time after which the gopher becomes prey to hawks if he stays outside a hole. The second line of input contains two floating point numbers: the (xs,ys) coordinates of the gopher starting hole. The third line contains the (xt, yt) coordinates of the target hole. Each Subsequent line of input contains two floating point numbers: the (x,y) coordinates of a gopher hole. All distances are in metres, to the nearest mm.

Output
If the gopher can make it to the target hole, the output line should read "Yes, visiting n other holes.", where n is the minimal number of intermediate holes the gopher has to visit. If the gopher cannot make it the output line should read "No." There are not more than 1000 gopher holes and all coordinates are between -10000 and +10000.

Sample Input

3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000

Sample Output

Yes, visiting 2 other holes.

Hint
Sample input 2
5 1
0.000 0.000
0.000 550.000
179.000 0.000
0.000 301.000

Output for sample input 2
No.

我的程序：
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
struct node
{
	int point;
	int step;
};
double x[1100],y[1100];
bool flag[1100]={false};
int main()
{
	int i,v,t;
	scanf("%d%d",&v,&t);
	t*=60;
	double beginX,beginY,endX,endY;
	scanf("%lf%lf%lf%lf",&beginX,&beginY,&endX,&endY);
	int n=1;
	while(scanf("%lf%lf",x+n,y+n)!=EOF)
		n++;
	x[0]=beginX;
	y[0]=beginY;
	x[n]=endX;
	y[n]=endY;

	node n1;//队列初始化
	n1.point=0;
	n1.step=0;
	queue<node> que;
	que.push(n1);

	int steps=0;
	while(true)
	{
		if(que.empty())
			break;
		node tmp=que.front();
		que.pop();//出队列
		for(i=1;i<=n;i++)
		{
			if(!flag[i])//标志是否进过队列
			{				
				double time=sqrt(pow(x[i]-x[tmp.point],2.0)+pow(y[i]-y[tmp.point],2.0))/v;
				if(time<t)
				{
					if(i==n)
					{
						steps=tmp.step;
						goto next;
					}
					else
					{
						node in;
						in.point=i;
						in.step=tmp.step+1;
						que.push(in);//进队列
						flag[i]=true;
					}
				}
			}
		}
	}
	next:
	if(steps!=0)
		printf("Yes, visiting %d other holes.\n",steps);
	else
		printf("No.\n");
	return 0;
}