ppt：http://pan.baidu.com/s/1eQBzFqE

入门知识汇总：经典DP： LIS LCS， 状态压缩DP 区间DP图论：MST ， 最短路三种算法（dijkstra ， bellman ford， floyd ），最大流， 双连通分量（点双连通，边双连通，强连通）数学：质因数分解，筛素数，数论的常用结论数据结构： 线段树，树状数组，字典树，kmp，哈希，平衡树（treap 或者 splay）搜索：普通dfs  bfs ， 双向广搜， 常用的剪枝策略。算法的中英文搜索，各种博客，不同的搜索引擎，找相应的题目，问题导向。

举两个栗子LIS，中英文叫法 最长不下降子序列 最长上升子序列 longest increasing subsequence解决什么样的问题：	对于一个序列，求最长的上升的子序列的长度。		1 4 6 3 7 4 8longest[i]:     1 2 3 2 4 2 55怎么输出LIS5：1 4 6 7 8怎么解决：动态规划是历史经验的总结，他把历史数据最好（优）的一面呈现出来，以供现在的决策，使得现在的决策达到最优，而现在也会成为以后的历史经验longest[i]： 以第i个数结尾的LIS的长度,是longest[i]i+1   (j<=i)#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[1100], longest[1010], shangyige[1100];void print(int id){	if(shangyige[id] != -1) {		print(shangyige[id]);	}	printf("%d ", a[id]);}int main(){	int n;	while(true) 	{	int ret = scanf("%d", &n);	if(ret == -1) break; 	for(int i = 0; i < n; i++) {		scanf("%d", &a[i]);	}	for(int i = 0; i < n; i++) {		longest[i] = 1;		shangyige[i] = -1;		for(int j = 0; j < i; j++)	 {			if(a[j] < a[i] && longest[j] + 1 > longest[i]) {				longest[i] = longest[j] + 1;				shangyige[i] = j;			}		}	}	int mx = 0, index = -1;	for(int i = 0; i < n; i++) {		if(longest[i] > mx) {			mx = longest[i];			index = i;		}	}	printf("%d\n", mx);	/*	int b[110], tot = 0;	for(int i = index; i != -1; i = shangyige[i]) {		b[tot++] = a[i];	}	for(int i = tot - 1; i >= 0; i--) {		printf("%d ",b[i]);	}	*///	print(index);//	puts("");	}	return 0;}、BFS （bread first search） 广度优先搜索 广搜解决什么样的问题：从一个状态到另一个状态的最短路，比如从迷宫的一个点到另一个点怎么解决:了解队列：first in first out类似于食堂排队买饭，先来的先买，买完的人离开，刚来的人插入到队伍最后面。#include <cstdio>#include <cstring>const int MAX_N = 310;const int MAX_M = 310;//需要的数据结构 struct Person{	int x, y, step;	//构造函数 	Person() {	}	Person(int _x, int _y, int _step) {		x = _x;		y = _y;		step = _step;			}};Person queue[MAX_N * MAX_M];int visited[MAX_N][MAX_M];// 0 1 int front, end;int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1}; int n, m;int bfs(int sx, int sy, int tx, int ty){//	return -1;	if(sx == tx && sy == ty) {		return 0;	}	front = 0, end = 0;	memset(visited, 0, sizeof(visited));	queue[end++] = Person(sx, sy, 0);		visited[sx][sy] = 1;	int last;	while(front < end) {		//把队首的元素取出来		Person first = queue[front];		front++;		if(first.step != last) {			puts("");		}		last = first.step;		//扩展下一层的元素 		for(int i = 0; i < 4; i++) {			int x = first.x + dir[i][0];			int y = first.y + dir[i][1];			if(x <= 0 || x > n || y <= 0 || y > m) {				continue;			}			if(visited[x][y] == 1) {				continue;			}			//printf("x=%d y=%d\n",x, y);			visited[x][y] = 1;			printf("新扩展了 ： x=%d y=%d step=%d\n", x, y, first.step + 1);			queue[end++] = Person(x, y, first.step + 1);			if(x == tx && y == ty) {				return first.step + 1;			}		}	}	return -99999;	}int main(){	int t;	while(1) {		scanf("%d%d", &n,&m);		int sx, sy, tx, ty;		sx=1,sy=1,tx=n, ty=m;		printf("%d\n",bfs(sx, sy, tx, ty));	}	return 0;}

ACM入门 训练方法