(总结一)poj简单动态规划

《(总结一)poj简单动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、例1：求一维数组屮连续数Z和的最大值。代码：#includeusingnamespacestd;inta[100];//记录一维数组intres[100];//resfil表示以第i个数为末尾的连续数Z和的最大值intmain(){inti,n,max;while(l){cin»n;if(!n)break;memset(res,0,sizeof(a)),max=-1270000;for(i=0;i0&&res]i・ll>0)res

2、Ul+二resell：//动态规划法if(res[i]>max)max=res[i];//打擂法}cout«max«endl;}return0;例2(pojl050)：求二维数组中子矩阵之和的最大值。(例1的拓展)代码：#includeusingnamespacestd;intallOlJLIOlJ;//记录二维数组intsum[101][101];//sum[i][j]表示第j列前i行的数之和intres[101][1011[101];//res[iliri2][j]表示从第订行到第i2行，以第

3、j个数为末尾的连续数Z和的最大值intmain(){inti,il,i2j,n,temp,max;while(l){cin»n;if(!n)break;memset(sum909sizeof(sum))9memset(res909sizeof(res));for(i=l;i<=n;i++)for(j=l;j<=n;j++){cin»a[i][j];//输入二维数组sum[i][j]=sum[i-l][j]+a[i][j];//求第j列前i行之和}max=-1270000;for(il=l;il<=n;il++)//类

4、似一维数组求最大和的方法，将一重循环改为三重循环for(i2=il;i2<=n;i2++)for(j=l;j<=n;j++){res[il]

5、i2

6、[j]=sum[i2][j]・sinn[il・l]Li];〃相当于一维数组中的第j个数if(res[il][i2Hi・ll>0)Fes[il][i21[il+=res[il][i21Li・ll;if(res[il][i2][j]>max)max=res[il][i2][j];}cout«max«endl;}return0;}例3(pojl458)：求最长公共子序列的长度。

7、代码：#include#includeusingnamespacestd;intres[500][500];//res[i][j]表示si屮第i个字符、s2屮笫j个字符之前的最长公共子序列长度intmax(inta,intb){returna>b?a:b;}intmain(){intij,nl,n2;stringsl,s2;while(l){cin»sl»s2;memset(res,0,sizeof(res)),nl=sl.length(),n2=s2.1ength();for(i

8、=0;i

9、l][i+l],res

10、l+l][i]);}cout«res[nl][n2]«endl;}return0;}例4(pojll63)：求三角形内可取得的最大和。#includeusingnamespacestd;inta[101][101];intres[101][101];//res[i][j]表

11、示从顶端到达位置(i,j)所取得的最大值intMax(intajntb){returna>b?a:b;}intmain(){intij,n,max;cin»n;while(n){for(i=0;ivn;i++)〃输入数据for(j=0;j<=i;j++)cin»a[i][j];res[O][O]=a[O][O];for(i=l;i

12、r(i=2;imax)max=res[n-l][j];cout«max«endl;ci