之前做过acm，总结出来了一些算法模板。这些是我在搞懂先自己写然后想大牛靠拢不断优化的结果，可能有些是大牛们的源代码，在此一并发出，希望对大家有所帮助，代码中可能有错，在此表示歉意。
动态规划模板
处理求矩阵的最大子矩
//************************************************************
//求a[n][m]的最大子矩阵
///计算从某固定行开始起连续列b[i,j]动态规划求最大值
int dp( const int *b,int m)
{
int sum ,max,i;
sum=max=b[0];
for(i=1;i
0)sum+=b[i];
else sum=b[i];
if(sum>max)max=sum;
}
return max;
}
//b[k]可以取到任意连续行的排列组合
max=-999999999;
for(i=0;i
max) max=dp(b,m); } } //************************************************************ 动态规划求最大面积 //************************************************************ { 首先开辟数组a[N],l[N],r[N] ////找出其左右区间比其大的区间长度 l[1]=1; r[n]=n; for (i=2; i<=n; ++i) { t=i; while (t>1 && a[i]<=a[t-1]) t=l[t-1]; l[i]=t; } for (i=n-1; i>=1; --i) { t=i; while (t
max) max=(r[i]-l[i]+1)*a[i]; } } //************************************************************ 最长公共子序列 //********************************************************* //算法1:时间复杂度为O(N*M),空间复杂度为O(N*N) const int MAXN=1000; char str1[MAXN],str2[MAXN]; int dp[MAXN][MAXN]; int LCS1(char *str1,char *str2) { int len1=strlen(str1); int len2=strlen(str2); int i,j; memset(dp,0,sizeof(dp)); for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else if(dp[i-1][j]>dp[i][j-1]) dp[i][j]=dp[i-1][j]; else dp[i][j]=dp[i][j-1]; } } return dp[len1][len2]; } //===============================================//算法2:时间复杂度为O(N*M),空间复杂度为O(N) const int MAXN=1000; char str1[MAXN],str2[MAXN]; int dp[2][MAXN];//采用滚动数组优化 int LCS2(char *str1,char *str2) { int len1=strlen(str1); int len2=strlen(str2); int i,j,k; memset(dp,0,sizeof(dp)); for(i=1;i<=len1;i++) { k=i&1; for(j=1;j<=len2;j++) { if(str1[i-1]==str2[j-1]) dp[k][j]=dp[k][j-1]+1; else if(dp[k^1][j]>dp[k][j-1]) dp[k][j]=dp[k^1][j]; else dp[k][j]=dp[k][j-1]; } } return dp[k][len2]; } //********************************************************* 最长公共递增子序列 //************************************************************ //其中a[n],b[n]分别存放俩序列 memset(dp,0,sizeof(dp)); max=0; for(i=0;i
b[j]&&dp[k]
>data[i][j]; } } for(j=1;j<=m;j++) dp[n][j]=data[n][j]; for(i=n-1;i>=1;i--) { for(j=i;j>=1;j--) { dp[i][j]=max(dp[i+1][j]+data[i][j],dp[i+1][j+1]+data[i][j]); } } } //************************************************************ 最长递增子序列 //求严格递增子序列的最长长度 //************************************************************ //算法1的时间复杂度为O(N*log(N)) const int MAXN=1000; int data[MAXN];//存放原始数据 int MaxV[MAXN];//MaxV[i]存放长度为i的严格递增子序列的最大值的最小值 //二分查找返回MaxV中大于等于x的组靠左的下标 int BinaryResearch(int x,int len) { int mid,low=1,high=len; while(low<=high) { mid=(low+high)>
>1; if(MaxV[mid]
MaxV[len])//比长度为len的子序列最大值大,直接加进末尾 MaxV[++len]=data[i]; else { int pos=BinaryResearch(data[i],len); MaxV[pos]=data[i]; } } return len; } //=============================================== //算法2的时间复杂度为O(N*N) int dp[MAXN]; //返回原序列中严格递增子序列的最长长度 int LIS1(int n) { int i,j,lmax; lmax=0; for(i=0;i
data[j]&&dp[j]+1>dp[i]) dp[i]=dp[j]+1; } if(dp[i]>lmax)lmax=dp[i]; } return lmax; } //************************************************************ 最大字段和 //************************************************************ void MSS(int n) { int i; int max=NINF; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { if(dp[i-1]<=0) dp[i]=data[i]; else dp[i]=dp[i-1]+data[i]; if(max
=weight;i--) dp[i]=max(dp[i],dp[i-weight]+value); } void CompletePack(int weight,int value,int lim) //对应完全背包的求法 { for(int i=weight;i<=lim;i++) dp[i]=max(dp[i],dp[i-weight]+value); } void MultiplePack(int weight,int value,int amount,int lim) //选定物品后的多重背包的求法 { if(weight*amount>=lim)CompletePack(weight,value,lim); else { for(int k=1;k
=da[i])//保证inc队列在start-i区间内的递增 rear2--; Inc[++rear2]=i; while(da[Dec[front1]]-da[Inc[front2]]>k) { //保证区间左端点向后滑动一个长度 if(Dec[front1]-Inc[front2]<0) { start=Dec[front1]+1; front1++; } else { start=Inc[front2]+1; front2++; } } //满足m<=Max-Min<=k if(da[Dec[front1]]-da[Inc[front2]]>=m) { if(i-start+1>ans) ans=i-start+1; } } return ans; } 并查