ACM动态规划问题简易模板(C++可编译)

三角形面积计算 (1)字典树模板 (2)求线段所在直线 (5)求外接圆 (5)求内接圆 (6)判断点是否在直线上 (8)简单多边形面积计算公式 (8)stein算法求最大共约数 (9)最长递增子序列模板——o(nlogn算法实现) (9)判断图中同一直线的点的最大数量 (10)公因数和公倍数 (12)已知先序中序求后序 (12)深度优先搜索模板 (13)匈牙利算法——二部图匹配BFS实现 (15)带输出路径的prime算法 (17)prime模板 (18)kruskal模板 (19)dijsktra (22)并查集模板 (23)高精度模板 (24)三角形面积计算//已知三条边和外接圆半径，公式为s = a*b*c/(4*R)double GetArea(double a, double b, double c, double R){return a*b*c/4/R;}//已知三条边和内接圆半径，公式为s = prdouble GetArea(double a, double b, double c, double r){return r*(a+b+c)/2;}//已知三角形三条边，求面积double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}//已知道三角形三个顶点的坐标struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};double GetArea(Point p1, Point p2, Point p3){double t =-p2.x*p1.y+p3.x*p1.y+p1.x*p2.y-p3.x*p2.y-p1.x*p3.y+p2.x*p3.y;if(t < 0) t = -t;return t/2;}字典树模板#include <stdio.h>#include <string.h>#include <memory.h>#define BASE_LETTER 'a'#define MAX_TREE 35000#define MAX_BRANCH 26struct{int next[MAX_BRANCH]; //记录分支的位置int c[MAX_BRANCH]; //查看分支的个数int flag; //是否存在以该结点为终止结点的东东，可以更改为任意的属性}trie[MAX_TREE];int now;void init(){now = 0;memset(&trie[now], 0, sizeof(trie[now]));now ++;}int add (){memset(&trie[now], 0, sizeof(trie[now]));return now++;}int insert( char *str){int pre = 0, addr;while( *str != 0 ){addr = *str - BASE_LETTER;if( !trie[pre].next[addr] )trie[pre].next[addr] = add();trie[pre].c[addr]++;pre = trie[pre].next[addr];str ++;}trie[pre].flag = 1;return pre;}int search( char *str ){int pre = 0, addr;while( *str != 0 ){addr = *str - BASE_LETTER;if ( !trie[pre].next[addr] )return 0;pre = trie[pre].next[addr];str ++;}if( !trie[pre].flag )return 0;return pre;}pku2001题，源代码：void check( char *str ){int pre = 0, addr;while(*str != 0){addr = *str - BASE_LETTER;if( trie[pre].c[addr] == 1) {printf("%c\n", *str);return;}printf("%c", *str);pre = trie[pre].next[addr];str ++;}printf("\n");}char input[1001][25];int main(){int i = 0,j;init();while(scanf("%s", input[i]) != EOF){getchar();insert(input[i]);i++;}for(j = 0; j < i; j ++){printf("%s ", input[j]);check(input[j]);}return 0;}求线段所在直线//*****************************线段所在的直线struct Line{double a, b, c;};struct Point{double x, y;}Line GetLine(Point p1, Point p2){//ax+by+c = 0返回直线的参数Line line;line.a = p2.y - p1.y;line.b = p1.x - p2.x;line.c = p2.x*p1.y - p1.x*p2.y;return line;}求外接圆//***************已知三角形三个顶点坐标，求外接圆的半径和坐标********************struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};struct TCircle{double r;Point p;}double distance(Point p1, Point p2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}TCircle GetTCircle(Point p1, Point p2, Point p3){double a, b, c;double xa,ya, xb, yb, xc, yc, c1, c2;TCircle tc;a = distance(p1, p2);b = distance(p2, p3);c = distance(p3, p1);//求半径tc.r = a*b*c/4/GetArea(a, b, c);//求坐标xa = p1.x; ya = p1.b;xb = p2.x; yb = p2.b;xc = p3.x; yc = p3.b;c1 = (xa*xa + ya*ya - xb*xb - yb*yb)/2;c2 = (xa*xa + ya*ya - xc*xc - yc*yc)/2;tc.p.x = (c1*(ya-yc) - c2*(ya-yb))/((xa-xb)*(ya-yc) - (xa-xc)*(ya-yb)); tc.p.y = (c1*(xa-xc) - c2*(xa-xb))/((ya-yb)*(xa-xc) - (ya-yc)*(xa-xb));return tc;}求内接圆struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};struct TCircle{double r;Point p;}double distance(Point p1, Point p2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}TCircle GetTCircle(Point p1, Point p2, Point p3){double a, b, c;double xa,ya, xb, yb, xc, yc, c1, c2, f1, f2;double A,B,C;TCircle tc;a = distance(p1, p2);b = distance(p3, p2);c = distance(p3, p1);//求半径tc.r = 2*GetArea(a, b, c)/(a+b+c);//求坐标A = acos((b*b+c*c-a*a)/(2*b*c));B = acos((a*a+c*c-b*b)/(2*a*c));C = acos((a*a+b*b-c*c)/(2*a*b));p = sin(A/2); p2 = sin(B/2); p3 = sin(C/2);xb = p1.x; yb = p1.b;xc = p2.x; yc = p2.b;xa = p3.x; ya = p3.b;f1 = ( (tc.r/p2)*(tc.r/p2) - (tc.r/p)*(tc.r/p) + xa*xa - xb*xb + ya*ya - yb*yb)/2;f2 = ( (tc.r/p3)*(tc.r/p3) - (tc.r/p)*(tc.r/p) + xa*xa - xc*xc + ya*ya - yc*yc)/2;tc.p.x = (f1*(ya-yc) - f2*(ya-yb))/((xa-xb)*(ya-yc)-(xa-xc)*(ya-yb)); tc.p.y = (f1*(xa-xc) - f2*(xa-xb))/((ya-yb)*(xa-xc)-(ya-yc)*(xa-xb));return tc;}判断点是否在直线上//**************判断点是否在直线上********************* //判断点p是否在直线[p1,p2]struct Point{double x,y;};bool isPointOnSegment(Point p1, Point p2, Point p0){//叉积是否为0，判断是否在同一直线上if((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) != 0)return false;//判断是否在线段上if((p0.x > p1.x && p0.x > p2.x) || (p0.x < p1.x && p0.x < p2.x)) return false;if((p0.y > p1.y && p0.y > p1.y) || (p0.y < p1.y && p0.y < p2.y)) return false;return true;}简单多边形面积计算公式struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};Point pp[10];double GetArea(Point *pp, int n){//n为点的个数，pp中记录的是点的坐标int i = 1;double t = 0;for(; i <= n-1; i++)t += pp[i-1].x*pp[i].y - pp[i].x*pp[i-1].y;t += pp[n-1].x*pp[0].y - pp[0].x*pp[n-1].y;if(t < 0) t = -t;return t/2;}stein算法求最大共约数int gcd(int a,int b){if (a == 0) return b;if (b == 0) return a;if (a % 2 == 0 && b % 2 == 0) return 2 * gcd(a/2,b/2); else if (a % 2 == 0) return gcd(a/2,b);else if (b % 2 == 0) return gcd(a,b/2);else return gcd(abs(a-b),min(a,b));}最长递增子序列模板——o(nlogn算法实现)#include <stdio.h>#define MAX 40000int array[MAX], B[MAX];int main(){int count,i,n,left,mid,right,Blen=0,num;scanf("%d",&count); //case的个数while(count--){scanf("%d",&n); //每组成员的数量Blen = 0;for(i=1;i<=n;i++)scanf("%d",&array[i]); //读入每个成员for(i=1;i<=n;i++){num = array[i];left = 1;right = Blen;while(left<=right){mid = (left+right)/2;if(B[mid]<num)left = mid+1;elseright = mid-1;}B[left] = num;if(Blen<left)Blen++;}printf("%d\n",Blen);//输出结果}return 1;}判断图中同一直线的点的最大数量#include <iostream>#include <cstdio>#include <memory>using namespace std;#define MAX 1010 //最大点的个数struct point{int x,y;}num[MAX];int used[MAX][MAX*2]; //条件中点的左边不会大于1000,just equal MAX int countN[MAX][MAX*2];#define abs(a) (a>0?a:(-a))int GCD(int x, int y){int temp;if(x < y){temp = x; x = y; y = temp;}while(y != 0){temp = y;y = x % y;x = temp;}return x;}int main(){int n,i,j;int a,b,d,ans;while(scanf("%d", &n)==1){//initeans = 1;memset(used, 0, sizeof(used));memset(countN, 0, sizeof(countN));//readfor(i = 0; i < n; i++)scanf("%d%d", &num[i].x, &num[i].y);for(i = 0; i < n-1; i++){for(j = i+1; j < n; j++){b = num[j].y-num[i].y;a = num[j].x-num[i].x;if(a < 0) //这样可以让（2，3）（－2，－3）等价{a = -a; b = -b;}d = GCD(a,abs(b));a /= d;b /= d; b += 1000;//条件中点的左边不会大于1000if(used[a][b] != i+1){used[a][b] = i+1;countN[a][b] = 1;}else{countN[a][b]++;if(ans < countN[a][b])ans = countN[a][b];}}//for}//forprintf("%d\n", ans+1);}return 0;}公因数和公倍数int GCD(int x, int y){int temp;if(x < y){temp = x; x = y; y = temp;}while(y != 0){temp = y;y = x % y;x = temp;}return x;}int beishu(int x, int y){return x * y / GCD(x,y);}已知先序中序求后序#include <iostream>#include <string>using namespace std;string post;void fun(string pre, string mid){if(pre == "" || mid == "") return;int i = mid.find(pre[0]);fun(pre.substr(1,i), mid.substr(0,i));fun(pre.substr(i+1, (int)pre.length()-i-1), mid.substr(i+1, (int)mid.length()-i-1));post += pre[0];}int main(){string pre, mid;while(cin >> pre){cin >> mid;post.erase();fun(pre, mid);cout << post << endl;}return 0;}深度优先搜索模板int t; //t用来标识要搜索的元素int count; //count用来标识搜索元素的个数int data[m][n]; //data用来存储数据的数组//注意，数组默认是按照1……n存储，即没有第0行//下面是4个方向的搜索,void search(int x, int y){data[x][y] = *; //搜索过进行标记if(x-1 >= 1 && data[x-1][y] == t){count++;search(x-1,y);}if(x+1 <= n && data[x+1][y] == t){count++;search(x+1,y);}if(y-1 >= 1 && data[x][y-1] == t){count++;search(x,y-1);}if(y+1 <= n && data[x][y+1] == t){count++;search(x,y+1);}}//下面是8个方向的搜索void search(int x, int y){data[x][y] = *; //搜索过进行标记if(x-1 >= 1){if(data[x-1][y] == t){count++;search(x-1,y);}if(y-1 >= 1 && data[x-1][y-1] == t) {count++;search(x-1,y-1);}if(y+1 <= n && data[x-1][y+1] == t) {count++;search(x-1,y+1);}}if(x+1 <= n){if(data[x+1][y] == t){count++;search(x+1,y);}if(y-1 >= 1 && data[x+1][y-1] == t) {count++;search(x+1,y-1);}if(y+1 <= n && data[x+1][y+1] == t) {count++;search(x+1,y+1);}}if(y-1 >= 1 && data[x][y-1] == t){count++;search(x,y-1);}if(y+1 <= n && data[x][y+1] == t){count++;search(x,y+1);}}匈牙利算法——二部图匹配BFS实现//匈牙利算法实现#define MAX 310 //二部图一侧顶点的最大个数int n,m; //二分图的两个集合分别含有n和m个元素。

acm动态规划例题Problem A:简单的图形覆盖Time Limit:1000MS Memory Limit:65536KTotal Submit:201 Accepted:104Description有一个2*n 的方格,要用若干个1*2的模块覆盖,模块可以横放,也可以竖放.问对于给定的n(n<=100),有多少种不同的覆盖方法.Input有多个测试用例,每个用例占一行,为一个正整数nOutput对于每个测试用例,输出一行相应的结果Sample Input9 11Sample Output55 144分析：f(n)=??>-+-==2)2()1(2211n n f n f n n #include int A[101]; int main() {int n,i;while(scanf("%d",&n)!=EOF) {A[0]=1;A[1]=2;if(n==1||n==0) printf("%d\n",A[0]);else if(n==2) printf("%d\n",A[1]);else{for(i=2;i<n;i++)< p="">A[i]=A[i-1]+A[i-2];printf("%d\n",A[i-1]);}}return 0;}Problem B:最大子段和Time Limit:1000MS Memory Limit:65536KTotal Submit:574 Accepted:299Description有一组数,如-2 5 4 -3 7 的最大子段和是13, 是从5到7.Input第一行输入一个n(1〈N〈=100 ) 表示这一组数有多长,第二行是N个数. 测试案例有多个,n=0时结束.Output输出这一组数的最大子段和.Sample Input5-2 5 4 -3 7109 -3 8 -28 98 -30 -20 50 -24 10Sample Output13 98分析： A-2 5 4 -3 7 B 表示A0~Ai 数段中包含第i 个元素的最大子段和-2 59613B[i]=??>+-=0]}[],[]1[max{0][i i A i A i B i i A#include int A[101]; int B[101]; int main() {int n,i,max;scanf("%d",&n); while(n!=0) {for(i=0;i<="">return 0; }Problem C:最长公共子序列Time Limit:1000MS Memory Limit:65536KTotal Submit:164 Accepted:99Description我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列,使得对j=1,2,...k,有Xij=zj.比如Z=＜a,b,f,c＞是X=＜a,b,c,f,b,c＞的子序列.现在给出两个序列X和Y,任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列.Input输入包括多组测试数据.每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列.两个字符串之间由若干个空格9开.Output对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度.Sample Inputabcfbc abfcabprogramming contestabcd mnpSample Output42分析Z[i][j]=[1][1]1[][]max{[1][],[][1]}[][]Z i j X i Y jZ i j Z i j X i Y j--+=--≠下标0 1 2 3 4 5 6 Z[i][j] a b c f b c0 0 0 0 0 0 0 01 a 0 1 1 1 1 1 12 b 0 1 2 2 2 2 23 f 0 1 2 2 3 3 34 c 0 1 2 3 3 3 45 a 0 1 2 3 3 3 46 b 0 1 2 3 3 4 4X，Y下标从0开始，Z[i][j] 下标有效的从1开始#include#includechar x[201];char y[201];int z[200][200];int main(){int i,j,s,t,max;while(scanf("%s%s",x,y)!=EOF){s=strlen(x);t=strlen(y);for(i=0;i<s;i++)< p="">z[i][0]=0;for(j=0;j<t;j++)< p="">z[0][j]=0;for(i=1;i<=s;i++)for(j=1;j<=t;j++){if(x[i-1]==y[j-1]) z[i][j]=z[i-1][j-1]+1;else{if(z[i-1][j]>=z[i][j-1]) z[i][j]=z[i-1][j];else z[i][j]=z[i][j-1];}}max=z[0][0];for(i=0;i<=s;i++)for(j=0;j<=t;j++)if(z[i][j]>max) max=z[i][j];printf("%d\n",max);}return 0;}Problem D:最长上升子序列Time Limit:1000MS Memory Limit:65536KTotal Submit:456 Accepted:239 Description一个数的序列bi,当b1<=b2<=b3..<=bn的时候,称这个序列是上升的。

ACM Standard Code LibraryHuang WeiComputer Science and EngineeringAssociation of ProgramingInformation Engineering CollegeHangzhou Dianzi UniversityApril, 2007ACM 算法模板集Contents一.常用函数与STL二.重要公式与定理1. Fibonacci Number2. Lucas Number3. Catalan Number4. Stirling Number(Second Kind)5. Bell Number6. Stirling's Approximation7. Sum of Reciprocal Approximation8. Young Tableau9. 整数划分10. 错排公式11. 三角形内切圆半径公式12. 三角形外接圆半径公式13. 圆內接四边形面积公式14. 基础数论公式三.大数模板四.数论算法1. Greatest Common Divisor最大公约数2. Prime素数判断3. Sieve Prime素数筛法4. Module Inverse模逆元5. Extended Euclid扩展欧几里德算法6. Modular Linear Equation模线性方程(同余方程)7. Chinese Remainder Theorem中国余数定理五.图论算法1. 最小生成树(Kruscal算法)2. 最小生成树(Prim算法)3. 单源最短路径(Bellman-ford算法)4. 单源最短路径(Dijkstra算法)5. 全源最短路径(Folyd算法)6. 拓扑排序7. 网络预流和最大流8. 网络最小费用最大流9. 网络最大流(高度标号预流推进)10. 最大团11. 最大二分图匹配(匈牙利算法)六.几何算法1. 几何模板2. 球面上两点最短距离3. 三点求圆心坐标七.专题讨论1. 树状数组2. 字典树3. 后缀树4. 线段树5. 并查集6. 二叉堆7. 逆序数(归并排序)8. 树状DP9. 欧拉路10. 八数码11. 高斯消元法12. 字符串匹配(KMP算法)13. 全排列,全组合第一章常用函数和STL一.常用函数#include <stdio.h>int getchar( void ); //读取一个字符, 一般用来去掉无用字符char *gets( char *str ); //读取一行字符串#include <stdlib.h>void * malloc( size_t size ); //动态内存分配, 开辟大小为 size 的空间void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) ); //快速排序Sample:int compare_ints( const void* a, const void* b ){int* arg1 = (int*) a; int* arg2 = (int*) b;if( *arg1 < *arg2 ) return -1;else if( *arg1 == *arg2 ) return 0;else return 1;}int array[] = { -2, 99, 0, -743, 2, 3, 4 }; int array_size = 7;qsort( array, array_size, sizeof(int), compare_ints );#include <math.h>//求反正弦, arg∈[-1, 1], 返回值∈[-pi/2, +pi/2]double asin( double arg );//求正弦, arg为弧度, 弧度=角度*Pi/180.0, 返回值∈[-1, 1]double sin( double arg );//求e的arg次方double exp( double arg );//求num的对数, 基数为edouble log( double num );//求num的根double sqrt( double num );//求base的exp次方double pow( double base, double exp );#include <string.h>//初始化内存, 常用来初始化数组void* memset( void* buffer, int ch, size_t count );memset( the_array, 0, sizeof(the_array) );//printf是它的变形, 常用来将数据格式化为字符串int sprintf( char *buffer, const char *format, ... );sprintf(s, "%d%d", 123, 4567); //s="1234567"//scanf是它的变形, 常用来从字符串中提取数据int sscanf( const char *buffer, const char *format, ... );Sample:char result[100]="24 hello", str[100]; int num;sprintf( result, "%d %s", num,str );//num=24;str="hello" ;//字符串比较, 返回值<0代表str1<str2, =0代表str1=str2, >0代表str1>str2 int strcmp( const char *str1, const char *str2 );二.常用STL[标准container概要]vector<T> 大小可变的向量, 类似数组的用法, 容易实现删除list<T> 双向链表queue<T> 队列, empty(), front(), pop(), push()stack<T> 栈, empty(), top(), pop(), push()priority_queue<T> 优先队列, empty(), top(), pop(), push()set<T> 集合map<key,val> 关联数组, 常用来作hash映射[标准algorithm摘录]for_each() 对每一个元素都唤起（调用）一个函数find() 查找第一个能与引数匹配的元素replace() 用新的值替换元素, O(N)copy() 复制（拷贝）元素, O(N)remove() 移除元素reverse() 倒置元素sort() 排序, O(N log(N))partial_sort() 部分排序binary_search() 二分查找merge() 合并有序的序列, O(N)[C++ String摘录]copy() 从别的字符串拷贝empty() 判断字符串是否为空erase() 从字符串移除元素find() 查找元素insert() 插入元素length() 字符串长度replace() 替换元素substr() 取子字符串swap() 交换字符串第二章重要公式与定理1.Fibonacci Number0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 …Formula:2.Lucas Number1, 3, 4, 7, 11, 18, 29, 47, 76, 123...Formula:3.Catalan Number1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012…Formula:Application:1)将n + 2 边形沿弦切割成n个三角形的不同切割数Sample:n = 2;n = 3;2)n + 1个数相乘, 给每两个元素加上括号的不同方法数Sample:n = 2; (1 (2 3)), ((1 2) 3)n = 3; (1 (2 (3 4))), (1 ((2 3) 4)) , ((1 2) (3 4)), ((1 (2 3)) 4), (((1 2) 3) 4)3)n 个节点的不同形状的二叉树数(严《数据结构》P.155)4)从n * n 方格的左上角移动到右下角不升路径数Sample:n = 2;n = 3;4.Stirling Number(Second Kind)S(n, m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m 个无标号的盒子中, 要求无一为空, 其不同的方案数Formula:Special Cases:5.Bell Numbern 个元素集合所有的划分数Formula:6.Stirling's Approximation7.Sum of Reciprocal ApproximationEulerGamma = 0.57721566490153286060651209;8.Young TableauYoung Tableau(杨式图表)是一个矩阵, 它满足条件:如果格子[i, j]没有元素, 则[i+1, j]也一定没有元素如果格子[i, j]有元素a[i, j],则[i+1, j]要么没有元素, 要么a[i+1, j] > a[i, j] Y[n]代表n个数所组成的杨式图表的个数Formula:Sample:n = 3;9.整数划分将整数n分成k份, 且每份不能为空, 任意两种分法不能相同1) 不考虑顺序for(int p=1; p<=n ;p++)for(int i=p; i<=n ;i++)for(int j=k; j>=1 ;j--)dp[i][j] += dp[i-p][j-1];cout<< dp[n][k] <<endl;2) 考虑顺序dp[i][j] = dp[i-k][j-1]; (k=1..i)3) 若分解出来的每个数均有一个上限mdp[i][j] = dp[i-k][ j-1]; (k=1..m)10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式1)模取幂2) n的约数的个数若n满足, 则n的约数的个数为第三章大数模板/**** **** **** **** **** ***** Function Name : BigNumber* Description : BigNumber's HPC* Author : HuangWei* Last Edited : 07.4.11**** **** **** **** **** ****/#include <iostream>#include <string>#include <sstream>#include <memory>#include <algorithm>#define BASE 1000 // 基数#define DIG 1100 // 存储using namespace std;class BigNumber{private:int data[DIG]; // 数据区int len; // 记录长度public:BigNumber() {len=1;memset(data,0,sizeof(data));data[0]=1;}BigNumber(int); // 输入默认十进制BigNumber(char*);BigNumber(const BigNumber &);// 类型转换BigNumber & Num_BNum(int); //把一个整数转换成BigNumber型的BigNumber & Str_BNum(char*); //把一个字符串类型的转换成BigNumber型的int Int();string Str();// HPCBigNumber & Add(const BigNumber &);BigNumber & Sub(const BigNumber &);BigNumber & Mul(const BigNumber &);BigNumber & Div(int);BigNumber & Mod(int);BigNumber & operator=(const BigNumber &);int Bigger(const BigNumber &) const;BigNumber operator + (const BigNumber &);BigNumber operator - (const BigNumber &);BigNumber operator * (const BigNumber &);BigNumber operator / (int);BigNumber operator % (int);BigNumber & operator += (const BigNumber &); BigNumber & operator -= (const BigNumber &); BigNumber & operator *= (const BigNumber &); BigNumber & operator /= (int);BigNumber & operator %= (int);};BigNumber & BigNumber::Num_BNum(int b){len=1; memset(data,0,sizeof(data));data[0] = 1;if(b < 0) {b = -b;data[0] = -1;}while(b > 0) {data[ len++ ] = b % BASE;b /= BASE;}return *this;}BigNumber & BigNumber::Str_BNum(char* sb) {int t=0, d=1, b=0, slen=strlen(sb), i;len=1; memset(data,0,sizeof(data));data[0] = 1;if(sb[0] == '-') data[0] = -1, b=1;for(i=slen-1; i>=b ;i--) {while(t >= BASE || d > BASE) {data[ len++ ] = t % BASE;t /= BASE;d = 10;}t += (sb[i]-'0') * d;d *= 10;}while(t > 0) {data[ len++ ] = t % BASE;t /= BASE;}return *this;}int BigNumber::Int(){istringstream sin;int v;sin.str( this->Str() );sin >> v;return v;} //这个函数的用法还是第一次看到，没看懂string BigNumber::Str(){int i,base_len=0;ostringstream sout;if(len == 1) {sout << '0';//sout << endl;return sout.str();}if(data[0] < 0) sout << "-";sout << data[len-1];i = BASE;while(i > 1) {base_len++;i /= 10;}for(i=len-2; i>0 ;i--) {sout.width(base_len);sout.fill('0');sout << data[i];}//sout << endl;return sout.str();} //这个函数也没有看懂BigNumber::BigNumber(int b){this->Num_BNum(b);}BigNumber::BigNumber(char* sb){this->Str_BNum(sb);}// -1 a<b, 0 a==b, 1 a>bBigNumber::BigNumber(const BigNumber & b){len = b.len; memcpy(data,b.data,sizeof(data));}int BigNumber::Bigger(const BigNumber & b) const {int i,flag;if(data[0] ==1 && b.data[0] ==1) flag = 1;else if(data[0] ==1 && b.data[0] ==-1) return 1;else if(data[0] ==-1 && b.data[0] ==1) return -1;else flag = -1;if(len > b.len) return flag;else if(len == b.len) {for(i=len-1; i>0 ;i--)if(data[i] > b.data[i]) return flag;}if(i == 0) return 0;return -flag;} //比较函数BigNumber & BigNumber::Add(const BigNumber & b) {int i;if(data[0] * b.data[0] != 1) {data[0] = -data[0];Sub(b);data[0] = -data[0];return *this;}len= len > b.len ? len : b.len;for(i=1; i<len ;i++) {data[i] += b.data[i];if(data[i] >= BASE) {data[i+1]++;data[i] -= BASE;}}if(data[i] > 0) len = i+1;return *this;} //加上b这个大数BigNumber & BigNumber::Sub(const BigNumber & b) {int i;if(data[0] * b.data[0] != 1) {data[0] = -data[0];Add(b);data[0] = -data[0];return *this;}len= len > b.len ? len : b.len;for(i=1; i<len ;i++) {data[i] -= b.data[i];if(data[i] < 0) {data[i+1]--;data[i] += BASE;}}if(data[len] < 0) {for(i=0; i<=len ;i++)data[i] = -data[i];for(i=1; i<len ;i++)if(data[i] < 0) {data[i+1]--;data[i] += BASE;}}while(data[len-1] == 0) len--;return *this;}BigNumber & BigNumber::Mul(const BigNumber & b) {BigNumber bt;int i,j,up;int temp,temp1;bt.data[0] = data[0] * b.data[0];for(i=1; i<len ;i++) {up = 0;for(j=1; j<b.len ;j++) {temp = data[i] * b.data[j] + bt.data[i+j-1] + up;if(temp >= BASE) {temp1 = temp % BASE;up = temp / BASE;bt.data[i+j-1] = temp1;}else {up = 0;bt.data[i+j-1] = temp;}}if(up != 0) bt.data[i+j-1] = up;}bt.len = i+j;while(bt.data[bt.len-1] == 0) bt.len--;*this=bt;return *this;}BigNumber & BigNumber::Div(int b){BigNumber bt;int i,down = 0;if(b < 0) bt.data[0] = -data[0] , b = -b;else bt.data[0] = data[0];for(i=len-1; i>=1 ;i--) {bt.data[i] = (data[i] + down * BASE) / b;down = data[i] + down * BASE - bt.data[i] * b;}bt.len = len;while(bt.data[bt.len-1] == 0) bt.len--;*this=bt;return *this;}BigNumber & BigNumber::Mod(int b){int temp = 0, up = 0, i;for(i=len-1; i>=1 ;i--) {temp = data[i];temp += up * BASE;up = temp % b;}if(data[0] < 0) up = -up;*this = up;return *this;}BigNumber & BigNumber::operator = (const BigNumber & b) {len = b.len; memcpy(data,b.data,sizeof(data)); return *this;}BigNumber BigNumber::operator + (const BigNumber & b) {BigNumber bt=*this; return bt.Add(b);}BigNumber BigNumber::operator - (const BigNumber & b) {BigNumber bt=*this; return bt.Sub(b);}BigNumber BigNumber::operator * (const BigNumber & b) {BigNumber bt=*this; return bt.Mul(b);}BigNumber BigNumber::operator / (int b){BigNumber bt=*this; return bt.Div(b);}BigNumber BigNumber::operator % (int b){BigNumber bt=*this; return bt.Mod(b);}BigNumber & BigNumber::operator += (const BigNumber & b) {return this->Add(b);}BigNumber & BigNumber::operator -= (const BigNumber & b) {return this->Sub(b);}BigNumber & BigNumber::operator *= (const BigNumber & b) {return this->Mul(b);}BigNumber & BigNumber::operator /= (int b){return this->Div(b);}BigNumber & BigNumber::operator %= (int b){return this->Mod(b);}第四章数论算法1.Greatest Common Divisor最大公约数int GCD(int x, int y){int t;while(y > 0) {t = x % y;x = y;y = t;}return x;}2.Prime素数判断bool is_prime(int u){if(u == 0 || u == 1) return false;if(u == 2) return true;if(u%2 == 0) return false;for(int i=3; i <= sqrt(u) ;i+=2)if(u%i==0) return false;return true;}3.Sieve Prime素数筛法const int M = 1000; // M : sizebool mark[M]; // true : prime numbervoid sieve_prime(){memset(mark, true, sizeof(mark));mark[0] = mark[1] = false;for(int i=2; i <= sqrt(M) ;i++) {if(mark[i]) {for(int j=i*i; j < M ;j+=i)mark[j] = false;}}}4.Module Inverse模逆元// ax ≡ 1 (mod n)int Inv(int a, int n){int d, x, y;d = extended_euclid(a, n, x, y);if(d == 1) return (x%n + n) % n;else return -1; // no solution}5.Extended Euclid扩展欧几里德算法//如果GCD(a,b) = d, 则存在x, y, 使d = ax + by// extended_euclid(a, b) = ax + byint extended_euclid(int a, int b, int &x, int &y){int d;if(b == 0) {x = 1; y = 0; return a;}d = extended_euclid(b, a % b, y, x);y -= a / b * x;return d;}6.Modular Linear Equation模线性方程(同余方程) //如果GCD(a, b)不能整除c, 则ax + by = c 没有整数解// ax ≡ b (mod n) n > 0//上式等价于二元一次方程ax – ny = bvoid modular_linear_equation(int a, int b, int n){int d, x, y, x0;d = extended_euclid(a, n, x, y);if( b%d == 0) {x0 = ( x*(b/d) ) % n; // x0 : basic solutionint ans = n;for(int i=0; i < d ;i++) {ans = ( x0 + i*(n/d) ) % n;cout << ans << endl;}}else cout << "no solution" << endl;}7.Chinese Remainder Theorem中国余数定理// x ≡ b[i] (mod w[i]), i∈[1, len-1]// 前提条件w[i] > 0, 且w[]中任意两个数互质int chinese_remainder(int b[], int w[], int len){int i, d, x, y, m, n;x = 0; n = 1;for(i=0; i < len ;i++) n *= w[i];for(i=0; i < len ;i++) {m = n / w[i] ;d = extended_euclid(w[i], m, x, y);x = (x + y*m*b[i]) % n;}return (n + x%n) % n;}第五章图论算法1.最小生成树(Kruscal算法)/**** **** **** **** **** ***** Function Name : 最小生成树(Kruscal算法)* Description : ZJU 1203 Swordfish O(E*LogE)**** **** **** **** **** ****/#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>using namespace std;struct struct_edges{int bv,tv; //bv 起点 tv 终点double w; //权值};struct_edges edges[10100]; //边集struct struct_a{double x;double y;};struct_a arr_xy[101];int point[101],n,e; //n 顶点数, e 边数(注意是无向网络)double sum;int kruscal_f1(int point[], int v){int i = v;while(point[i] > 0) i = point[i];return i;}bool UDlesser(struct_edges a, struct_edges b){return a.w < b.w;}void kruscal() //只需要准备好n，e，递增的边集edges[]即可使用{int v1,v2,i,j;for(i=0; i<n ;i++) point[i]=0;i = j = 0;while(j<n-1 && i<e) {v1 = kruscal_f1(point, edges[i].bv);v2 = kruscal_f1(point, edges[i].tv);if(v1 != v2) {sum += edges[i].w; //注意sum初始为0point[v1]=v2;j++;}i++;}}int main(){int k,i,j;cin>>n;k=0;while(n != 0) {sum=0;k++;for(i=0; i<n ;i++)cin>>arr_xy[i].x>>arr_xy[i].y;e=0;for(i=0; i<n ;i++) //从0开始计数for(j=i+1; j<n ;j++) //注意是无向网络{if(i == j) continue;edges[e].bv=i;edges[e].tv=j;edges[e].w=sqrt((arr_xy[i].x-arr_xy[j].x)*(arr_xy[i].x-arr_xy[j].x)+( arr_xy[i].y-arr_xy[j].y)*(arr_xy[i].y-arr_xy[j].y));e++;}sort(edges,edges+e,UDlesser); //得到一个递增的边集，注意是从0开始计数kruscal();printf("Case #%d:\n",k); //cout<<"Case #"<<k<<":"<<endl;printf("The minimal distance is: %.2f\n",sum); //输出sumcin>>n;if(n != 0) printf("\n");}}2.最小生成树(Prim算法)/**** **** **** **** **** ***** Function Name : 最小生成树(Prim算法)* Description : ZJU 1203 Swordfish O(N^2)**** **** **** **** **** ****/#include <iostream>#include <cmath>#include <cstdio>using namespace std;double sum, arr_list[101][101], min;int i, j, k=0, n;struct struct_a{float x;float y;};struct_a arr_xy[101];struct struct_b{int point;float lowcost;};struct_b closedge[101];void prim(int n) //prim 需要准备：n顶点数 arr_list[][]顶点的邻接矩阵也是从0开始计数{int i,j,k;k=0;for(j=0; j<n ;j++) {if(j != k) {closedge[j].point = k;closedge[j].lowcost = arr_list[k][j];}}closedge[k].lowcost=0;for(i=0; i<n ;i++) {min=10000;for(j=0; j<n ;j++) {if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) {k = j;min = closedge[j].lowcost;}}sum += closedge[k].lowcost; //不要改成sum+=min; sum即为所求值 closedge[k].lowcost = 0;for(j=0; j<n ;j++) {if(arr_list[k][j] < closedge[j].lowcost) {closedge[j].point = k;closedge[j].lowcost = arr_list[k][j];}}}}/*arr_list[][]= Wij 如果Vi, Vj有边0 如果i=j无限大如果没有边*/int main(){cin>>n;while(n != 0) {sum=0;k++;for(i=0; i<n ;i++)cin>>arr_xy[i].x>>arr_xy[i].y;for(i=0; i<n ;i++)for(j=0; j<n ;j++) //得到邻接矩阵arr_list[][]arr_list[i][j]=arr_list[j][i]=sqrt((arr_xy[i].x-arr_xy[j].x)*(arr_xy[i].x-arr_xy[j].x)+(arr_xy[i].y-arr_xy[j].y)*(arr_xy[i].y-arr_xy[j].y));prim(n);cout<<"Case #"<<k<<":"<<endl;printf("The minimal distance is: %.2f\n",sum);cin>>n;if(n!=0) printf("\n");}}3.单源最短路径(Bellman-ford算法)/**** **** **** **** **** ***** Function Name : 单源最短路径(Bellman-ford算法)* Description : 可允许有负权**** **** **** **** **** ****/#include <stdio.h>#define MAX 100#define MAXNUM 1000000typedef struct graphnode{int vexnum; //顶点数int arcnum; //边数int gra[MAX][MAX]; //图}Graph;Graph *G;//arc数组中存储的第一个顶点到其他顶点的最短路径//结果存在dis数组中int dis[MAX];int arc[MAX][MAX];void bellman(Graph *G){int i,j;bool sign;for(i=0; i < G->vexnum ;i++) dis[i]=MAXNUM;dis[1] = 0;sign = true;for(i=1; i < G->vexnum ;i++) {sign = false;for(j=0; j < G->arcnum ;j++) {if(dis[ arc[j][0] ] < MAXNUM&& dis[ arc[j][1] ] > dis[ arc[j][0] ] + G->gra[ arc[j][0] ][ arc[j][1] ]) {dis[ arc[j][1] ]=dis[ arc[j][0] ] + G->gra[ arc[j][0] ][ arc[j][1] ];sign = true;}}}return;}4.单源最短路径(Dijkstra算法)/**** **** **** **** **** ***** Function Name : 单源最短路径 (Dijkstra算法)* Description : 贪心, O(N^2), 不能有负权**** **** **** **** **** ****/int matrix[200][200],n; //matrix[][], 30000表示无限大,即无边.否则为有边,其值为边的权值void Dijkstra(int x,int y) //起点Vx 终点Vy{int i,j,k,path[40000],mark[40000];int min,dist[40000];for(i=1;i<=n;i++) {mark[i] = 0;dist[i] = matrix[x][i];path[i] = x;}mark[x] = 1;do {min=30000;k=0;for(i=1;i<=n;i++)if(mark[i]==0 && dist[i]<min) {min = dist[i];k = i;}if(k) {mark[k] = 1;for(i=1;i<=n;i++)if(matrix[k][i]<30000 && min+matrix[k][i]<dist[i]) {dist[i] = min + matrix[k][i];path[i] = k;}}}while(k);cout<<dist[y]<<endl; //dist[y] 的值就是从Vx 到 Vy 的最短路径值//如果希望得到路径，加入如下代码：do {cout<<k<<"<--";k = path[k];}while(k!=x);cout<<x<<endl;}5.全源最短路径(Folyd算法)/**** **** **** **** **** ***** Function Name : 全源最短路径(Folyd算法)* Description : DP, O(N^3)**** **** **** **** **** ****///初始化//min_graph[i][j]=graph[i][j];//path[i][j]=j;void Floyd(){int i,j,k;for(k=0;k<vertex_number;k++) {for(i=0;i<vertex_number;i++) {for(j=0;j<vertex_number;j++) {if((graph[i][k]==-1) || (graph[k][j]==-1)) continue;if((min_graph[i][j]==-1) || (min_graph[i][j] > graph[i][k]+graph[k][j])) {min_graph[i][j] = graph[i][k]+graph[k][j]; /*最短路径值*/path[i][j] = k; /*最短路径*/}}}}}6.拓扑排序/**** **** **** **** **** ***** Function Name : 拓扑排序**** **** **** **** **** ****///degree[] 每个结点的入度//f[] 每个结点所在的层void Toplogical_sort(){int i,j;bool p=true;top=0;while(p) {p=false;top++;for(i=1;i<=n;i++)if(degree[i]==0) {p=true;f[i]=top;}for(i=1;i<=n;i++)if(f[i]==top) {for(j=1;j<=n;j++)if(map[i][j]) degree[j]--;degree[i]=-1;}}top--;}7.网络预流和最大流int rel[1000][10000]; //全局变量int pre[1000];//计算网络流//如果是二分图的匹配, 可以先对其进行网络预流以简化后续的查找int pre_flow(int n,vector<int> * v){int ret = 0;int i,j,t,t1;for(i = 0 ; i < v[0].size() ; i++){t = v[0][i]; //t是与节点0相邻接的点for(j = 0 ; j < v[t].size() ; j++){t1 = v[t][j]; //与t相邻接的点if(rel[t1][n - 1] > 0){ret++;rel[0][t]--, rel[t][0]++;rel[t][t1]--, rel[t1][t]++;rel[t1][n - 1]--, rel[n - 1][t1]++;break;}}}return ret;}/*网络中求最大流参数含义: n代表网络中节点数,第0节点为源点, 第n－1节点为汇点rel是个二维数组, rel[i][j]代表从节点i到节点j的流量v[]是一个节点数组, v[i]包含与节点i相邻接的所有节点返回值: 最大流量*/int max_flow(int n,vector<int> * v){int ret = 0,i;int t,t1,tm;queue<int> q;const int Infinite = 2000000000;while(1){for(t = 0 ; t < n ; t++) pre[t] = -1;while(!q.empty()) q.pop();q.push(0);while(!q.empty()){ //find a augmenting path using breath-first searcht = q.front();q.pop();if(t == n - 1) break; //到达汇点for(i = 0 ; i < v[t].size() ; i++){ //对于t相邻接的所有点查找可行路径 t1 = v[t][i];if(rel[t][t1] > 0 && pre[t1] == -1){pre[t1] = t;q.push(t1);}}}if(q.empty() && t != n - 1) break;tm = Infinite; //此处寻找路径最小值在二分图中可省略while(t != 0){ //find the minimal num in the patht1 = pre[t];if(rel[t1][t] < tm) tm = rel[t1][t];t = t1;}// tm = 1; //二分图中t = n - 1;while(t != 0){ //change the relationt1 = pre[t];rel[t1][t] -= tm;rel[t][t1] += tm;t = t1;}ret += tm;}return ret;}8.网络最小费用最大流/**** **** **** **** **** ****网络中最小费用最大流参数含义: np代表网络中的总节点数, v是网络节点的邻接表cost为最后求得的最小费用, mf为求得的最大流算法: 初始最小费用及最大流均为0，不断寻找可增广路增广路对应的单位费用最小并且可流修改残留网络及cost，mf. 直到无可增广路为止。

1、0-1背包#include <stdio.h>#include <stdlib.h>//背包问题/*测试数据：输入：8 238 4 5 1 6 6 7 37 8 3 3 4 9 6 2输出：1 0 1 0 1 0 1 1*/int num,c;int v[10];int w[10];int m[10][30];//设m[i][j],则表示在前i个物品中，背包大小是j的情况下，背包所装东西的最大价值void knapsack(){int n=num-1;int jmax,i,j;if(w[n]<c) jmax=w[n];else jmax=c;for(i=0;i<jmax;i++)m[n][i]=0;for(i=w[n];i<=c;i++)m[n][i]=v[n];for(i=n-1;i>0;i--){if(w[i]<c) jmax=w[i];else jmax=c;for(j=0;j<jmax;j++)m[i][j]=m[i+1][j];for(j=w[i];j<=c;j++){if(m[i+1][j]<m[i+1][j-w[i]]+v[i])m[i][j]=m[i+1][j-w[i]]+v[i];elsem[i][j]=m[i+1][j];}}m[0][c]=m[1][c];if(c>=w[0]){if(m[0][c]<m[1][c-w[0]]+v[0])m[0][c]=m[1][c-w[0]]+v[0];}}void trackback(int *x){int n=num-1;int i;for(i=0;i<n;i++){if(m[i][c]==m[i+1][c]) x[i]=0;else{x[i]=1;c=c-w[i];}}if(m[n][c]>0) x[n]=1;else x[n]=0;}int main(){int i,x[10],j;scanf("%d %d",&num,&c);for(i=0;i<num;i++)scanf("%d",&v[i]);for(i=0;i<num;i++)scanf("%d",&w[i]);knapsack();for(i=0;i<=c;i++) printf("%3d",i);printf("\n");for(i=0;i<num;i++){for(j=0;j<=c;j++)printf("%3d",m[i][j]);printf("\n");}trackback(x);for(i=0;i<num;i++)printf("%d ",x[i]);printf("\n");return 0;}2、KMP算法#include<iostream>#include<string.h>using namespace std;inline void BuildNext(const char* pattern, size_t length, unsigned int* next){unsigned int i, t;i = 1;t = 0;next[1] = 0;while(i < length + 1){while(t > 0 && pattern[i - 1] != pattern[t - 1]){t = next[t];}++t;++i;if(pattern[i - 1] == pattern[t - 1]){next[i] = next[t];}else{next[i] = t;}}//pattern末尾的结束符控制，用于寻找目标字符串中的所有匹配结果用while(t > 0 && pattern[i - 1] != pattern[t - 1]){t = next[t];}++t;++i;next[i] = t;}unsigned int KMP(const char* text, size_t text_length, const char* pattern, size_t pattern_length, unsigned int* matches){unsigned int i, j, n;unsigned int next[pattern_length + 2];BuildNext(pattern, pattern_length, next);i = 0;j = 1;n = 0;while(pattern_length + 1 - j <= text_length - i){if(text[i] == pattern[j - 1]){++i;++j;//发现匹配结果，将匹配子串的位置，加入结果if(j == pattern_length + 1){matches[n++] = i - pattern_length;j = next[j];}}else{j = next[j];if(j == 0){++i;++j;}}//返回发现的匹配数return n;}int main(){char a[20],b[20];int n1,n2,n;unsigned int match[100];cin>>a;n1=strlen(a);//待匹配串cin>>b;n2=strlen(b);//模板串n=KMP(a,n1,b,n2,match);cout<<n<<endl;for(int i=0;i<n;i++)cout<<match[i]<<' ';}3、最大子段和#include<iostream>#include<stdio.h>using namespace std;int main(){int T,n;int a[50000];int hd[50000],tl[50000];scanf("%d",&T);while(T--){scanf("%d",&n);int i,temp,max;;for(i = 0;i < n;i++)scanf("%d",&a[i]);//hd[],left -> rightmax = hd[0] = a[0];for(i = 1;i < n;i++){temp = a[i] + hd[i - 1];hd[i] = temp > a[i] ? temp : a[i];}for(i = 1;i < n;i++){hd[i] = max > hd[i] ? max : hd[i];max = hd[i];//tl[],right -> leftmax = tl[n - 1] = a[n - 1];for(i = n - 2;i >= 0;i--){temp = a[i] + tl[i + 1];tl[i] = temp > a[i] ? temp : a[i];}for(i = n - 2;i >= 0;i--){tl[i] = max > tl[i] ? max : tl[i];max = tl[i];}max = hd[0] + tl[1];for(i = 1;i < n - 1;i++){temp = hd[i] + tl[i + 1];max = max > temp ? max : temp;}printf("%d\n",max);}return 0;}4、最长公共子序列（不严格连续）#include <stdio.h>#include <string.h>#define MAXLEN 100void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) {int i, j;for(i = 0; i <= m; i++)c[i][0] = 0;for(j = 1; j <= n; j++)c[0][j] = 0;for(i = 1; i<= m; i++){for(j = 1; j <= n; j++){if(x[i-1] == y[j-1]){c[i][j] = c[i-1][j-1] + 1;b[i][j] = 0;}else if(c[i-1][j] >= c[i][j-1]){c[i][j] = c[i-1][j];b[i][j] = 1;}else{c[i][j] = c[i][j-1];b[i][j] = -1;}}}}void PrintLCS(int b[][MAXLEN], char *x, int i, int j) {if(i == 0 || j == 0)return;if(b[i][j] == 0){PrintLCS(b, x, i-1, j-1);printf("%c ", x[i-1]);}else if(b[i][j] == 1)PrintLCS(b, x, i-1, j);elsePrintLCS(b, x, i, j-1);}int main(int argc, char **argv){char x[MAXLEN] = {"ABCBDAB"};char y[MAXLEN] = {"BDCABA"};int b[MAXLEN][MAXLEN];int c[MAXLEN][MAXLEN];int m, n;m = strlen(x);n = strlen(y);LCSLength(x, y, m, n, c, b);PrintLCS(b, x, m, n);return 0;}5、最长公共子序列（不严格连续）#include<iostream>#include<cstdio>#include<memory.h>using namespace std;const int N = 505;int num1[N],num2[N],f[N][N];int main(){int t,n,m;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&num1[i]);scanf("%d",&m);for(int j=1;j<=m;j++)scanf("%d",&num2[j]);memset(f,0,sizeof(f));int answer=0;int ma;for(int i=1;i<=n;i++){ma=0;for(int j=1;j<=m;j++){f[i][j]=f[i-1][j];if(num1[i]>num2[j]&&f[i-1][j]>ma)ma=f[i-1][j];if(num1[i]==num2[j])f[i][j]=ma+1;}}for(int j=0;j<=m;j++)answer=max(answer,f[n][j]);printf("%d\n",answer);if(t!=0)printf("\n");}return 0;}6、最大子矩阵和#include <iostream>#include<memory.h>using namespace std;//求最大连续子矩阵和，动态规划，O(n^3) of time:/*输入41 -4 3 -8-3 5 2 -32 -1 8 1-1 1 -2 -4输出14*/int max_sum(int n, int *arr){ //求单个序列的最大连续子串和int result=0;int b=0;for(int i=0;i<n;i++){if(b>0) b+=arr[i];else b=arr[i];if(b>result) result=b;}return result;}int max_sum2(int m, int n, int **arr){int result=0;int *b=new int[n];for(int i=0;i<m;i++){memset(b,0,sizeof(int)*n);for(int j=i;j<m;j++){for(int k=0;k<n;k++)b[k]+=arr[j][k];//b[k]=arr[i][k]+arr[i+1][k]+...+arr[j][k]//从例子来说，当i=1,j=2时，有b[k]=arr[1][k]+arr[2][k],这时取到maxint max=max_sum(n,b);if(max>result) result=max;}}delete b;return result;}int main(){int N;cin>>N;int i,j;int **arr=new int*[N];for(i=0;i<N;i++){arr[i]=new int[N];for(j=0;j<N;j++)cin>>arr[i][j];}cout<<max_sum2(N,N,arr)<<endl;for(i=0;i<N;i++)delete arr[i];delete arr;return 0;}7、石子合并问题#include <iostream>#include <stdio.h>using namespace std;//石头合并问题PKU 1086 动态规划/*输入：44 1 2 3输出：*/#define MAX 1000000000int a[202];//每个石头的重量long f[202][202];//f[i][j]，第i个石头分到第j个石头合并的最小代价long sum[202][202];//sum[i][j],第i个石头到第j个石头的重量之和void print(int num){int i,j;for(i=1;i<=num;i++){for(j=1;j<=num;j++)printf("%3d",f[i][j]);cout<<endl;}cout<<endl;}void cal(int num){int i,j,k,min,d;for(i=1;i<=num;i++)f[i][i]=0;//不合并时的代价for(i=1;i<num;i++){sum[i][i]=a[i];for(j=i+1;j<=num;j++){sum[i][j]=sum[i][j-1]+a[j];}}sum[num][num]=a[num];for(d=1;d<=num-1;d++){for(i=1;i<=num-d;i++){j=i+d;min=MAX;//i..k为一堆石头，k+1,k+2...j为另一堆石头//f[i][j]为f[i][k]+f[k+1][j]+sum[i][j]的最小值(i<=j<k)for(k=i;k<j;k++)if(min>f[i][k]+f[k+1][j]+sum[i][j]) min=f[i][k]+f[k+1][j]+sum[i][j];f[i][j]=min;print(num);}}}int main(){int num,i;scanf("%d",&num);for(i=1;i<=num;i++)cin>>a[i];cal(num);cout<<f[1][num]<<endl;return 0;}8、最大乘积#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>using namespace std;//添加乘号得到最大乘积动态规划#define NMAX 12#define CMAX 7__int64 f[NMAX][CMAX];//f[i][j],长度为i,用了j个乘号后的最大值char str[22];void print(int num,int k){ //用于调试时打印f[][]int i,j;for(i=0;i<num;i++){for(j=1;j<=k;j++)printf("%6d",f[i][j]);cout<<endl;}cout<<endl;// system("pause");}int conv(int start,int num){ //在str[i]中，以start为起点，num为长度所表示的数字int sum,i;sum=0;for(i=1;i<=num;i++){sum*=10;sum+=str[start+i-1]-'0';}return sum;}void cal(int num,int chen){int i,j,temp,k;for(i=0;i<num;i++){ //初始化，不用乘号时的情况f[i][0]=conv(0,i+1);}for(j=1;j<=chen;j++){for(i=j;i<num;i++){temp=0;for(k=0;k<i;k++){//a1,a2,a3..an用j个乘号连接//看成是a1,a2...ak已经用j-1个乘号连接，//然后再与后面的ak+1,ak+2..an组成的数用1个乘号连接if(temp<f[k][j-1]*conv(k+1,i-k))temp=f[k][j-1]*conv(k+1,i-k);}f[i][j]=temp;//找到局部的最大乘积}// print(num,chen);}}int main(){int num,chen;//num为字符串长度while(scanf("%d%d",&num,&chen)!=EOF){scanf("%s",&str);cal(num,chen);printf("%I64d\n",f[num-1][chen]);}return 0;}。

动态规划——C编辑最短距离C - 编辑距离时间限制: 1000⼥⼠内存限制: 65536KB 64位输⼊输出格式: %I64d & %I64u提交描述Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below: Deletion: a letter in x is missing in y at a corresponding position.Insertion: a letter in y is missing in x at a corresponding position.Change: letters at corresponding positions are distinctCertainly, we would like to minimize the number of all possible operations.IllustrationA G T A A G T * A G G C| | | | | | |A G T * C * T G A C G CDeletion: * in the bottom lineInsertion: * in the top lineChange: when the letters at the top and bottom are distinctThis tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we would be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it likeA G T A A G T A G G C| | | | | | |A G T C T G * A C G Cand 4 moves would be required (3 changes and 1 deletion).In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where n ≥ m.Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.Write a program that would minimize the number of possible operations to transform any string x into a string y.InputThe input consists of the strings x and y prefixed by their respective lengths, which are within 1000.OutputAn integer representing the minimum number of possible operations to transform any string x into a string y.Sample Input10 AGTCTGACGC11 AGTAAGTAGGCSample Output4题⽬⼤意：给出两个字符串X,Y，求出从X——>Y的最⼩操作次数，只可以删除，添加，修改⼀个字符。