系统性训练，励志刷完挑战程序设计竞赛-代码整理43~68【初级篇】

本文主要是介绍系统性训练，励志刷完挑战程序设计竞赛-代码整理43~68【初级篇】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2014年9月4日大概完成到这边了。编写了几天突然感觉到cpp很上手。现在码的速度也提上去了。

/*
刚开始不明白到底是干什么的。后来仔细想想，我检查是弱爆了。
简单就是意思就是请求组合n中选m的种，即n的m划分。不重复。使用dp存储。求解组合类问题思路有了吧。当然用组合工程直接求也行。
DP计数:从n物品中划分出m种不同的组合 4
3
100004
*/#include<iostream>
using namespace std;
int n,m,M;
const int MAXN=1<<10;
int dp[MAXN][MAXN];void input(){scanf("%d%d%d",&n,&m,&M);	
}//dp[i][j] j的i划分总数 
void sovle(){dp[0][0]=1;for(int i=1;i<=m;i++)for(int j=0;j<=n;j++){if(j-i>=0)dp[i][j]=(dp[i][j-i]+dp[i-1][j])%M;elsedp[i][j]=dp[i-1][j];}printf("%d\n",dp[m][n]);
}int main(){input();sovle();	return 0;	
}

/*
最后使用stl中的函数快速的求解二分上下限的方法不错。值得学习。5
4 2 3 1 53
*/
#include <iostream>
using namespace std;
const int MAXN=1<<10;
int n,a[MAXN],dp[MAXN],INF=(1<<31)-1;void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d",&a[i++]);		
}//dp[i],a[i]个元素结尾的最长上升子序列的值void sovle1(){int ans=0;for(int i=0;i<n;i++){dp[i]=1;for(int j=0;j<i;j++){if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);	}	ans=max(ans,dp[i]);	}	printf("%d\n",ans);
}void sovle2(){fill(dp,dp+n,INF);for(int i=0;i<n;i++){*lower_bound(dp,dp+n,a[i])=a[i];}printf("%d\n",lower_bound(dp,dp+n,INF)-dp); //数组名dp返回的是数组首地址，l_b方法同样是dp的数组的地址号，相差12/4(int %d输出)=3 printf("%d\n",lower_bound(dp,dp+n,INF));printf("%d\n",dp);
}
int main(){input();sovle1();sovle2();return 0;	
}

/*3
3 5 8
3 2 2
17Yes
*/#include<iostream>
using namespace std;const int MAXN=1<<10;
int n,a[MAXN],m[MAXN],K,dp[MAXN][MAXN];void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d%d",&a[i],&m[i++]);scanf("%d",&K);	
}//dp[i+1][j]=前i个元素相加和得到j时,i元素的剩余个数
//3类，1:i-1得到j，此时i元素的剩余量为mi
//2:i 前i中加和出j-ai，那么第i种剩余量为k，所以剩余此时i的剩余量为k-1个 
void sovle(){memset(dp,-1,sizeof(dp));dp[0][0]=0; //初始化for(int i=0;i<n;i++)for(int j=0;j<=K;j++){if(dp[i][j]>=0){  //说明i-1之和=j了。 i+1对应的是i剩余m[i] dp[i+1][j]=m[i];}else if(j<a[i] || dp[i+1][j-a[i]]<=0){ //j<a[i]不满足选择a[i],dp[i+1][j-a[i]]<=0即前i元素之和等于j-a[i]时，i的元素剩余量<=0。所以dp[i+1][j]=-1;即不能选 dp[i+1][j]=-1;}else{dp[i+1][j]=dp[i+1][j-a[i]]-1;  //dp[i+1][j-a[i]] ,前i种加和j-a[i]时，i的剩余量>0，那么dp[i+1][j]=K-1了。 }	}/* for(int i=0;i<=n;i++){for(int j=0;j<=K;j++){printf("%d ",dp[i][j]); }printf("\n");	}*/if(dp[n][K]>=0)printf("Yes\n");elseprintf("No\n");}int main(){input();sovle();		return 0;
}

/*
如果w数值范围较大，需要转换dp。即将内层循环次数最小，价值v代替 
//dp[i+1][j]，挑选前i个物品的总价值j时，总重量的最小值 4
2 3
1 2
3 4
2 2
57
*/#include<iostream>
using namespace std;
const int MAX_N=100,MAX_V=100;
const int MAXN=1<<20;
int n,W,w[MAXN],v[MAX_V],dp[MAX_N+1][MAX_N*MAX_V+1];int INF=1<<11;void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d%d",&w[i],&v[i++]);scanf("%d",&W);	}void sovle(){fill(dp[0],dp[0]+MAX_N*MAX_V+1,INF);dp[0][0]=0;for(int i=0;i<n;i++){for(int j=0;j<=MAX_N*MAX_V;j++){if(j<v[i])dp[i+1][j]=dp[i][j];elsedp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);}}int ans=0;for(int i=0;i<=MAX_N*MAX_V;i++){//printf("%d  ",dp[n][i]);if(dp[n][i]<=W) ans=i;}printf("%d\n",ans);}int main(){input();sovle();	return 0;	
}

/*
下面是三种不同的技巧。不过答案是14.不是书上的10.难道我错了？
话说完全背包与01背包状态转移一样。3
3 4
4 5
2 3
710
*/ 
#include<iostream>
using namespace std;
const int MAXN=1<<10;
int n,W,w[MAXN],v[MAXN],dp[MAXN][MAXN],dpp[MAXN];void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d%d",&w[i],&v[i++]);scanf("%d",&W);	
}
//从前i种物品挑选总重量小于j时的总价值最大，此时与01背包问题相同 
//dp[i+1][j]=dp[i][j];
//dp[i+1]][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
void sovle1(){for(int i=0;i<n;i++)for(int j=0;j<=W;j++){if(j<w[i])dp[i+1][j]=dp[i][j];elsedp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);//dp[i+1][j]=(j<w[i])?dp[i][j]:max(dp[i][j],dp[i+1][j-w[i]]+v[i]);} printf("%d\n",dp[n][W]);
}//重复利用数组 
void sovle2(){for(int i=0;i<n;i++)for(int j=w[i];j<=W;j++){dpp[j]=max(dpp[j],dpp[j-w[i]]+v[i]);}printf("%d\n",dpp[W]);	
}//滚动二维数组，类似dp[2][MAXN] ,x=x&1,交叉奇偶 
void sovle3(){memset(dp,0x00,sizeof(dp));for(int i=0;i<n;i++)for(int j=0;j<=W;j++){if(j<w[i])dp[(i+1)&1][j]=dp[i&1][j];elsedp[(i+1)&1][j]=max(dp[i&1][j],dp[(i+1)&1][j-w[i]]+v[i]);//dp[i+1][j]=(j<w[i])?dp[i][j]:max(dp[i][j],dp[i+1][j-w[i]]+v[i]);} printf("%d\n",dp[n&1][W]);} int main(){input();sovle1();sovle2();sovle3();	return 0;
}

/*
2014阿里巴巴笔试题有一道是关于最长公共子序列lcp问题的，不过也可以转化为lcs问题。请看下面的方法就明白了。经典dp:lcs问题 
si+1=tj+1  dp[i+1][j+1]=dp[i][j]+1;此处另外三项相等
其他  dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);选择(si+1,ti),(si,ti+1)2个子串中的的最大值 4
4
abcd
becd3
2
*/
#include <iostream>
using namespace std;
const int MAXN=1<<10;
char s[MAXN],t[MAXN];
int n,m,dp[MAXN][MAXN];void input(){scanf("%d%d",&n,&m);scanf("%s%s",&s,&t);
}//求解dp[n][m] ,lcs问题 
void sovle1(){for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i]==t[j])dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}}printf("%d\n",dp[n][m]);
}//求解lcs连续公共子串 
void sovle2(){memset(dp,0x00,sizeof(dp));int max=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i]==t[j]){dp[i+1][j+1]=dp[i][j]+1;max=max<dp[i+1][j+1]?dp[i+1][j+1]:max;//printf("%d\n",max);	}else{dp[i+1][j+1]=0;	//非连续=0	}		}}/*for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){printf("%d ",dp[i][j]);	}printf("\n");}*/printf("%d\n",max);}int main(){input();sovle1();sovle2();return 0;
}

 /*
使用dp的时候一定要确定好状态，以及转移代价。然后求解dp。求解dp一般从边界开始递推，多的情况下有n^3次的复杂度求解。普通的dp为n^2，内层循环尽量大，
外层循环尽量小，可以减少cpu的切换，还有提高缓存命中率，一定程度上在机器本身上减少了运行代价。编程艺术上面都这么来的，其实书上写的也有局限性，只是作者没有
注意到实际情况。不过这样来写只是根据不同的编译器确定的。因为锅测试了下。如果不开编译器优化，基本没有差距。有的情况下还会有相反代价的运行。
看来有时候真的需要实践，实践是检验真理唯一标准，。一定木错。4
2 3
1 2
3 4
2 2
57
*/
#include<iostream>
using namespace std;
const int MAXN=1<<7;
int w[MAXN],v[MAXN],n,W,dp[MAXN][MAXN]; void input(){scanf("%d",&n);int i=0;while(i<n){scanf("%d %d",&w[i],&v[i]);i++;	}//while(--i>=0)printf("--%d %d\n",w[i],v[i]);	scanf("%d",&W);
}
//从第i件物品挑选小于j的重量 
int rec(int i,int j){if(dp[i][j]>=0) return dp[i][j];int res;if(i==n) res=0;else if(j<w[i]){res=rec(i+1,j);}else{//选择与不选择 res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); 	}return dp[i][j]=res;
}//枚举 
void sovle1(){memset(dp,-1,sizeof(dp));printf("%d\n",rec(0,W));		
}//dp[i][j] ,从第i个物品挑选出总重量小于j时，总价值最大， 
void sovle2(){//memset(dp,0,sizeof(dp));for(int i=0;i<=W;i++){dp[n][i]=0;}for(int i=n-1;i>=0;i--)for(int j=0;j<=W;j++){if(j<w[i]){dp[i][j]=dp[i+1][j];  //上，右方向计算dp 			} else{dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);  //[]扩错第二个参数，尼玛，调试半个小时，坑死我了 //第二个参数思维方向为递归选择最大值，保持dp[i][j]的价值总和最大 }			}			printf("%d\n",dp[0][W]);for(int i=0;i<n;i++){for(int j=0;j<=W;j++){printf("%d ",dp[i][j]);}	printf("\n");}
}//dp[i+1][j]，从前i个物品挑选出总重量不超过j物品的总价值最大 
void sovle3(){memset(dp,0,sizeof(dp));for(int i=0;i<n;i++)for(int j=0;j<=W;j++){if(j<w[i])dp[i+1][j]=dp[i][j];else dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);}printf("%d\n",dp[n][W]);
}int main(){input();sovle1();sovle2();	sovle3();return 0;
}

/*
修理栅栏,话说还用优先队列priority_queue存来维护最小值还是不错的。毕竟底层是二叉堆logn的代价
贪心策略：总的开销为所有的叶子节点的代价长度*深度之和。所以最短的板是叶子最深的节点，
次短的板是其兄弟节点。一直合并到根部即可 3
8 5 834
*/#include<iostream>
using namespace std;
const int MAXN=1<<11;
int N,L[MAXN];
typedef long long ll;void input(){scanf("%d",&N);int i=0;while(i<N){scanf("%d",&L[i++]);}	
}void sovle(){ll ans=0;while(N>1){int min1=0,min2=1;if(L[min1]>L[min2]) swap(min1,min2);for(int i=2;i<N;i++){if(L[i]<L[min1]){min2=min1;min1=i;}else if(L[i]<L[min2]){min2=i;}}	//合并 int t=L[min1]+L[min2];ans+=t;//将N-1的值转移到min2中,t转移到min1if(min1==N-1) swap(min1,min2);L[min1]=t;		L[min2]=L[N-1];	N--;	 	}	printf("%lld\n",ans);}int main(){input();sovle();return 0;
}

/*
囧，nn复杂度
贪心策略:向前走，R内最右侧，R外最近侧，循环至n结束即可 6
10
1 7 15 20 30 503
*/
#include<iostream>
using namespace std;
const int MAXN=1<<7;
int x[MAXN],n,r;void input(){scanf("%d",&n);scanf("%d",&r);int i=0;while(i<n){scanf("%d",&x[i++]);}		
}void sovle1(){int ans=0,a=0,f;sort(x,x+n);int cyc=-1; //防止过界循环标记 while(a<n){for(int i=a;i<n;i++){if(x[i]>(x[a]+r)){f=i-1;//printf("%d ",x[f]);break;	}}ans++;	for(int i=f;i<n;i++){if(x[i]>(x[f]+r)){a=i;if(cyc==a) goto loop ;	 cyc=a;//printf("%d ",a);break;}   }}loop:printf("%d\n",ans);	
}	void sovle2(){int i=0,ans=0;while(i<n){int s=x[i++];//s是没有覆盖的最左边的点 //一直向右前进到距离大于R的点 while(i<n && x[i]<=s+r)i++;int P=x[i-1];//标记点//一直向右前进至R之后未标记的点while(i<n&& x[i]<=P+r)i++;ans++;}printf("%d\n",ans);
}int main(){input();sovle1();sovle2();	return 0;
}

/*
贪心策略：比较s与s的逆序，较小者取其头部加入T即可 
6
ACDBCBABCBCD
*/
#include<iostream>
using namespace std;
const int MAXN=1<<8;
char s[MAXN];
int n;void input(){scanf("%d",&n);scanf("%s",&s);	
}
void sovle(){int a=0,b=n-1;bool f=true;while(a<=b){//判断取值左右 for(int i=0;i<n;i++){if(s[a+i]<s[b-i]){f=true;	break;}else if(s[a+i]>s[b-i]){f=false;break;}}if(f==true) printf("%c",s[a++]);else printf("%c",s[b--]);	}
}int main(){input();sovle();return 0;
}

这篇关于系统性训练，励志刷完挑战程序设计竞赛-代码整理43~68【初级篇】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---