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

1、1、0-1背包#include #include /背包问题/*测试数据：输入：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 v10;int w10;int m1030;/设mij,则表示在前i个物品中，背包大小是j的情况下，背包所装东西的最大价值void knapsack()int n=num-1;int jmax,i,j;if(wnc) jmax=wn;else jmax=c;for(i=0;ijmax;i+)mni=0;for(i=wn;i0;i-)if(wic) jmax=wi;else jmax

2、=c;for(j=0;jjmax;j+)mij=mi+1j;for(j=wi;j=c;j+)if(mi+1j=w0)if(m0cm1c-w0+v0)m0c=m1c-w0+v0;void trackback(int *x)int n=num-1;int i;for(i=0;i0) xn=1;else xn=0;int main()int i,x10,j;scanf(%d %d,&num,&c);for(i=0;inum;i+)scanf(%d,&vi);for(i=0;inum;i+)scanf(%d,&wi);knapsack();for(i=0;i=c;i+) printf(%3d,i);p

3、rintf(n);for(i=0;inum;i+)for(j=0;j=c;j+)printf(%3d,mij);printf(n);trackback(x);for(i=0;inum;i+)printf(%d ,xi);printf(n);return 0;2、KMP算法#include#includeusing namespace std;inline void BuildNext(const char* pattern, size_t length, unsigned int* next)unsigned int i, t;i = 1;t = 0;next1 = 0;while(i 0 &

4、 patterni - 1 != patternt - 1)t = nextt;+t;+i;if(patterni - 1 = patternt - 1)nexti = nextt;elsenexti = t;/pattern末尾的结束符控制，用于寻找目标字符串中的所有匹配结果用while(t 0 & patterni - 1 != patternt - 1)t = nextt;+t;+i;nexti = t;unsigned int KMP(const char* text, size_t text_length, const char* pattern, size_t pattern_le

5、ngth, unsigned int* matches)unsigned int i, j, n;unsigned int nextpattern_length + 2;BuildNext(pattern, pattern_length, next);i = 0;j = 1;n = 0;while(pattern_length + 1 - j a;n1=strlen(a);/待匹配串 cinb;n2=strlen(b);/模板串 n=KMP(a,n1,b,n2,match); coutnendl; for(int i=0;in;i+) coutmatchi ;3、最大子段和#include#i

6、ncludeusing namespace std;int main()int T,n;int a50000;int hd50000,tl50000;scanf(%d,&T);while(T-)scanf(%d,&n);int i,temp,max;for(i = 0;i rightmax = hd0 = a0;for(i = 1;i ai ? temp : ai;for(i = 1;i hdi ? max : hdi;max = hdi;/tl,right - leftmax = tln - 1 = an - 1;for(i = n - 2;i = 0;i-)temp = ai + tli

7、+ 1;tli = temp ai ? temp : ai;for(i = n - 2;i = 0;i-)tli = max tli ? max : tli;max = tli;max = hd0 + tl1;for(i = 1;i temp ? max : temp;printf(%dn,max);return 0;4、最长公共子序列（不严格连续）#include #include #define MAXLEN 100void LCSLength(char *x, char *y, int m, int n, int cMAXLEN, int bMAXLEN) int i, j; for(i

8、 = 0; i = m; i+) ci0 = 0; for(j = 1; j = n; j+) c0j = 0; for(i = 1; i= m; i+) for(j = 1; j = cij-1) cij = ci-1j; bij = 1; else cij = cij-1; bij = -1; void PrintLCS(int bMAXLEN, char *x, int i, int j) if(i = 0 | j = 0) return; if(bij = 0) PrintLCS(b, x, i-1, j-1); printf(%c , xi-1); else if(bij = 1)

9、PrintLCS(b, x, i-1, j); else PrintLCS(b, x, i, j-1);int main(int argc, char *argv) char xMAXLEN = ABCBDAB; char yMAXLEN = BDCABA; int bMAXLENMAXLEN; int cMAXLENMAXLEN; 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#include

10、#includeusing namespace std;const int N = 505;int num1N,num2N,fNN;int main()int t,n,m;scanf(%d,&t);while(t-)scanf(%d,&n);for(int i=1;i=n;i+)scanf(%d,&num1i);scanf(%d,&m);for(int j=1;j=m;j+)scanf(%d,&num2j);memset(f,0,sizeof(f);int answer=0;int ma;for(int i=1;i=n;i+)ma=0;for(int j=1;jnum2j&fi-1jma)ma

11、=fi-1j;if(num1i=num2j)fij=ma+1;for(int j=0;j=m;j+)answer=max(answer,fnj);printf(%dn,answer);if(t!=0)printf(n);return 0;6、最大子矩阵和#include #includeusing namespace std;/求最大连续子矩阵和，动态规划，O(n3) 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

12、 b=0;for(int i=0;i0) b+=arri;else b=arri;if(bresult) result=b;return result;int max_sum2(int m, int n, int *arr)int result=0;int *b=new intn;for(int i=0;im;i+)memset(b,0,sizeof(int)*n);for(int j=i;jm;j+)for(int k=0;kresult) result=max;delete b;return result;int main() int N;cinN;int i,j;int *arr=new

13、 int*N;for(i=0;iN;i+)arri=new intN;for(j=0;jarrij; coutmax_sum2(N,N,arr)endl;for(i=0;iN;i+)delete arri;delete arr;return 0;7、石子合并问题#include #include using namespace std;/石头合并问题 PKU 1086 动态规划/*输入：44 1 2 3输出：*/#define MAX int a202;/每个石头的重量long f202202;/fij，第i个石头分到第j个石头合并的最小代价long sum202202;/sumij,第i个石

14、头到第j个石头的重量之和void print(int num)int i,j;for(i=1;i=num;i+)for(j=1;j=num;j+)printf(%3d,fij);coutendl;coutendl;void cal(int num)int i,j,k,min,d;for(i=1;i=num;i+)fii=0;/不合并时的代价for(i=1;inum;i+)sumii=ai;for(j=i+1;j=num;j+)sumij=sumij-1+aj;sumnumnum=anum;for(d=1;d=num-1;d+)for(i=1;i=num-d;i+)j=i+d;min=MAX;/

15、i.k为一堆石头，k+1,k+2.j为另一堆石头/fij为fik+fk+1j+sumij的最小值(i=jk)for(k=i;kfik+fk+1j+sumij) min=fik+fk+1j+sumij;fij=min;print(num);int main()int num,i;scanf(%d,&num);for(i=1;iai;cal(num);coutf1numendl;return 0;8、最大乘积#include #include #include #include #include using namespace std;/添加乘号得到最大乘积 动态规划#define NMAX 12

16、#define CMAX 7_int64 fNMAXCMAX;/fij,长度为i,用了j个乘号后的最大值char str22;void print(int num,int k)/用于调试时打印f int i,j; for(i=0;inum;i+) for(j=1;j=k;j+) printf(%6d,fij); coutendl; coutendl;/ system(pause);int conv(int start,int num)/在stri中，以start为起点，num为长度所表示的数字int sum,i;sum=0;for(i=1;i=num;i+)sum*=10;sum+=strstart+i-1-0;return sum;void cal(int num,int chen)int i,j,temp,k;for(i=0;inum;i+)/初始化，不用乘号时的情况fi0=conv(0,i+1);for(j=1;j=chen;j+)for(i=j;inum;i+)temp=0;for(k=0;ki;k+)/a1,a2,a3.an用j个乘号连接/看成是a1,a2.ak已经用