资源描述:
《常用c++算法代码》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
实用标准文案堆石子游戏的问题(多元Huffman编码)问题描述:在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2堆最多选k堆石子合并成新的一堆,合并的费用为新的一堆的石子数。试设计一个算法,计算出将n堆石子合并成一堆的最大总费用和最小总费用。编程任务:对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。Input测试数据的第1行有2个正整数n和k,表示有n堆石子,每次至少选2堆最多选k堆石子合并。第2行有n个数,分别表示每堆石子的个数。Output输出最大总费用和最小总费用,用一空格隔开,每个答案一行。SampleInput73451312169522SampleOutput593199代码:#include#include#includeusingnamespacestd;boolcmp(inta,intb){ returna>b;}voidInsert(vector&f,intpos,intvalue){ for(inti=f.size()-1;i>pos;i--) { f[i]=f[i-1]; 精彩文档 实用标准文案} f[pos]=value;}intFind(vectorf,intvalue){ intpos=f.size()-1; while(pos>=0&&f[pos]f){ sort(f.begin(),f.end()); intMax; Max=0; while(f.size()>=2) { intsum=f[f.size()-1]+f[f.size()-2]; Max=Max+sum; f.resize(f.size()-1); f[f.size()-1]=sum; } returnMax;}intMinNum(vectorf,intlen){ sort(f.begin(),f.end(),cmp); intMin; Min=0; while(f.size()>=len) { intsum=0; for(inti=f.size()-1;i>=f.size()-len&&i>=0;i--) { sum=sum+f[i]; } Min=Min+sum; f.resize(f.size()-len+1); if(f.size()>len) 精彩文档 实用标准文案{ intpos=Find(f,sum); Insert(f,pos,sum); } elseif(f.size()!=1) { f[f.size()-1]=sum; for(inti=0;i>n>>m))returnfalse; vectorf(n); for(inti=0;i>f[i]; } intMax,Min; Max=MaxNum(f); while(f.size()%(m-1)!=1) { f.push_back(0); } Min=MinNum(f,m); cout<#includeusingnamespacestd;intn,k,m;constintlen=100000;inta[len];intb[len];intmain(){while(cin>>n>>k>>m){ inti; for(i=0;i>a[i]; b[i]=a[i]; if(i%k!=0) { b[i]=a[i]-a[i-1]; } } sort(b,b+n*k); intsum=0; for(i=0;iusingnamespacestd;constintlen=7001;intn,c;inta[len];intvisit[len];intGetRes(){ intp=0; inttemp=0; while(p>=0){ if(visit[p]==0) { visit[p]=1; temp+=a[p]; if(temp==c)return1; elseif(temp>c) { visit[p]=0; temp-=a[p]; } p++; } if(p>=n) { while(visit[p-1]==精彩文档 实用标准文案1) { p--; visit[p]=0; temp-=a[p]; if(p<1) { return0; } } while(visit[p-1]==0) { p--; if(p<1)return0; } visit[p-1]=0; temp-=a[p-1]; } } return0;}intmain(){while(scanf("%d%d",&n,&c)!=EOF){ memset(visit,0,sizeof(visit)); for(inti=0;iusingnamespacestd;constintlen=30;constintmaxWeight=4000;intn,m,cost;intw[len][len];//重量intc[len][len];//价钱intvisit[len];intpath[len];intminWeight=maxWeight;voidfindMinWeight(intcurrent,intweight,inti)//当前策略的价钱和最小重量{if(i>=n){ minWeight=weight; for(intj=0;j>n>>m>>cost){ minWeight=maxWeight; inti,j; for(i=0;i<2*n;i++) { for(j=0;j>c[i][j]; elsecin>>w[i-n][j]; } } findMinWeight(0,0,0); if(minWeight==maxWeight) cout<<"-1"<#includeusingnamespacestd;constintlen=10;inta[len][len];intb[len][len];intcc[len][len];intdd[len][len];intee[len][len];intn,cnt;voidinit(){for(inti=1;i<=n;i++){ for(intj=1;j<=n;j++) { a[i][j]=j; b[i][j]=j; cc[i][j]=0; }}}intok(intr,intc,intk,int精彩文档 实用标准文案fla){if(fla){ if(cc[a[r][c]][b[r][k]])return0; for(inti=1;i>n){ cnt=0; init(); backtrack(1,1); cout<usingnamespacestd;__int64f[40];voidinits(){inti,j;f[1]=1;for(i=2;i<=30;i++){ f[i]=0; for(j=1;j>n))returnfalse;printf("%I64d ",f[n]);returntrue;}intmain(){inits();while(run());return0;}整数因子分解问题大于1的正整数n可以分解为:n=x1*x2*…*xm。例如,当n=12时,共有8种不同的分解式:对于给定的正整数n,编程计算n共有多少种不同的分解式。代码:#includeusingnamespacestd;intcnt;voiddfs(intn){for(inti=n-1;i>=2;i--){ if(n%i==0) { cnt++; dfs(n/i); }}}intmain(){intn;while(cin>>n){ cnt=0; dfs(n); cout<#include#includeusingnamespacestd;doublef[10005][2];doubleff[10005][2];boolrun(){doubled,c,e,p;intn,k;if(!(cin>>d>>c>>e>>p>>n))returnfalse;int精彩文档 实用标准文案i,j;ff[0][0]=0;ff[0][1]=p;for(i=1;i<=n;i++){ cin>>ff[i][0]>>ff[i][1];}ff[n+1][0]=d;ff[n+1][1]=0;n++;fill(&f[0][0],&f[10003][1],0);doublet,x;doubley,a[2],b,q;for(i=1;i<=n;i++){ for(j=0;j=t) { y=(double)t/e; a[0]=f[j][0]-y; a[1]=f[j][1]; q=f[j][0]; } else { y=(double)((t-x)/e); if(y+f[j][0]>c)continue; a[0]=0; a[1]=f[j][1]+y*ff[j][1]; q=f[j][0]+y; } if(ff[j][1]=ff[k][0]) { 精彩文档 实用标准文案if(ff[k][1]f[i][0]) { if(a[1]<(a[0]-f[i][0])*ff[i][1]+f[i][1]) { f[i][0]=a[0]; f[i][1]=a[1]; } } elseif(a[0]#includeusingnamespacestd;constintlenn=10000;constintlens=500;intn,s;inta[lenn];intwait[lens];intfind(){intminTime=wait[0];intpos=0;for(inti=1;iwait[i]) { minTime=wait[i]; pos=i; }}returnpos;}精彩文档 实用标准文案intmain(){while(cin>>n>>s){ inti; for(i=0;i>a[i]; } sort(a,a+n); memset(wait,0,sizeof(wait)); doublesum=0; for(i=0;i#include#includeusingnamespacestd;charres[10001];inti,carry,len=1;voidmutiply(intn){ carry=0; char*h=res; for(i=0;i0) { mutiply(6); n2--; } else { mutiply(3); } } if(n2>0) { mutiply((int)pow(2.0,n2)); }}intmain(){ intn; res[0]=1; while(scanf("%d",&n)!=EOF) { if(n<=3) { printf("%d ",n); continue; } res[0]=1; len=1; f(n); for(i=len-1;i>=0;i--) { printf("%d",res[i]); } printf(" "); } return0;}精彩文档 实用标准文案——————————————————————————————————————————————————————有重复元素的排列问题问题描述:设R={r1,r2,...,rn}是要进行排列的n个元素。其中元素r1,r2,...,rn可能相同。试设计一个算法,计算出这n个元素的所有不同排列数。Input每组测试数据首先是n(1<=n<=500),接着是待排列的n个元素(小写字母)。Output输出排列总数。SampleInput4aaccSampleOutput6代码:#include#include#includeusingnamespacestd;constintlen=510;intn,ans;charlist[len];intok(intk,inti){if(i>k){ for(intt=k;t>n){ ans=0; for(inti=0;i>list[i]; } findResult(0); cout<usingnamespacestd;inta[22];intp[22][22];intq[22][22];intn;intsum=0;voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}voidBacktrack(intt){if(t>n){ ints=0; for(intj=0;j=sum)sum=s;}else{ for(inti=t;i<=n;i++) { swap(a[i],a[t]); Backtrack(t+1); swap(a[i],a[t]); }}}intmain(){inti,j;while(cin>>n){ for(i=0;i<=n;i++)a[i]=i; for(i=0;i>p[i][j]; } } for(i=0;i>q[i][j]; } } Backtrack(1); cout<#includeusingnamespacestd;inta[1111];intmain(){inti,n,j;for(i=1;i<=1001;i++){ a[i]=1;}for(i=1;i<=1001;i++){ for(j=1;j<=i/2;j++) { a[i]+=a[j]; }}while(cin>>n){ cout<#includeusingnamespacestd;constintlen=112;intd[len];stringa,b;intgetMin(intx,inty,intz){if(x<=y&&x<=z)returnx;elseif(y<=x&&y<=z)returny;elseif(z<=x&&z<=y)returnz;}intmain(){while(cin>>a>>b){ intm=a.size(); intn=b.size(); inti,j; for(i=1;i<=n;i++)d[i]=i; for(i=1;i<=m;精彩文档 实用标准文案i++) { inty=i-1; for(j=1;j<=n;j++) { intx=y; y=d[j]; intz=j>1?d[j-1]:i; intdel=a[i-1]==b[j-1]?0:1; d[j]=getMin(x+del,y+1,z+1); } } cout<