堆石子游戏的问题（多元Huffman编码）
问题描述：
在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。
编程任务：
对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。
Input
测试数据的第1 行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。
Output
输出最大总费用和最小总费用，用一空格隔开，每个答案一行。
Sample Input
7 3
45 13 12 16 9 5 22
Sample Output
593 199
代码：
#include #include #include using namespace std; bool cmp(int a, int b) { return a>b; } void Insert(vector { for (int i = f.size() - 1; i > pos; i--) { f[i] = f[i - 1]; } f[pos] = value; } int Find(vector { int pos = f.size() - 1; while (pos >= 0 && f[pos] < value) { pos--; } return pos + 1; } int MaxNum(vector { sort(f.begin(), f.end()); int Max; Max = 0; while (f.size() >= 2) { int sum = f[f.size() - 1] + f[f.size() - 2]; Max = Max + sum; f.resize(f.size() - 1); f[f.size() - 1] = sum; } return Max; } int MinNum(vector { sort(f.begin(), f.end(), cmp); int Min; Min = 0; while (f.size() >= len) { int sum = 0; for (int i = 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) { int pos = Find(f, sum); Insert(f, pos, sum); } else if (f.size() != 1) { f[f.size() - 1] = sum; for (int i = 0; i < f.size(); i++) { Min = Min + f[i]; } break; } else { break; } } return Min; } bool run() { int n, m; if (!(cin >> n >> m)) return false; vector for (int i = 0; i < n; i++) { cin >> f[i]; } int Max, Min; Max = MaxNum(f); while (f.size() % (m - 1) != 1) { f.push_back(0); } Min = MinNum(f, m); cout << Max << \" \" << Min << endl; return true; } int main() { while (run()); return 0; } —————————————————————————————————————————————————— 登山机器人问题 问题描述： 登山机器人是一个极富挑战性的高技术密集型科学研究项目，它为研究发展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。登山机器人可以携带有限的能量。在登山过程中，登山机器人需要消耗一定能量，连续攀登的路程越长，其攀登的速度就越慢。在对n 种不同类型的机器人作性能测试时，测定出每个机器人连续攀登1米，2米，…，k 米，所用的时间。现在要对这n个机器人作综合性能测试，举行机器人接力攀登演习。攀登的总高度为m 米。规定每个机器人只能攀登1次，每次至少攀登1 米，最多攀登k 米，而且每个机器人攀登的高度必须是整数，即只能在整米处接力。安排每个机器人攀登适当的高度，使完成接力攀登用的时间最短。 编程任务： 给定n 个登山机器人接力攀登的总高度m，及每个机器人连续攀登1 米，2 米，…，k米，所用的时间，编程计算最优攀登方案。 Input 每组测试数据的第一行是正整数n，k和m分别表示机器人的个数，每个机器人最多可以攀登的高度，和攀登的总高度。接下来的n行中，每行有k 个正整数，分别表示机器人连续攀登1米，2米，…，k 米所用的时间。 Output 输出最短攀登时间，每个答案一行。 Sample Input 5 10 25 24 49 75 102 130 160 192 230 270 320 23 48 75 103 139 181 224 274 344 415 22 49 80 180 280 380 480 580 680 780 25 51 80 120 170 220 270 320 370 420 23 49 79 118 158 200 250 300 350 400 Sample Output 727 代码： #include #include using namespace std; int n,k,m; const int len=100000; int a[len]; int b[len]; int main() { while(cin>>n>>k>>m) { int i; for(i=0; i cin>>a[i]; b[i]=a[i]; if(i%k!=0) { b[i]=a[i]-a[i-1]; } } sort(b,b+n*k); int sum=0; for(i=0; i cout< return 0; } ———————————————————————————————————————————————— 子集和问题 问题描述： 子集和问题的一个实例为〈S,c〉。其中，S={x1，x2，…，xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得 ∑x=c,(x∈S1)。试设计一个解子集和问题的回溯法。 Input 测试数据第1 行有2个正整数n和c，n 表示S 的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。 其中 n<7000 , c<10000000 。 Output 当问题无解时，输出“No”，否则输出“Yes”。 Sample Input 5 10 2 2 6 5 4 11 53 11 4 18 10 16 8 4 8 14 22 10 Sample Output Yes No 代码： #include using namespace std; const int len=7001; int n,c; int a[len]; int visit[len]; int GetRes(){ int p = 0; int temp = 0; while(p >= 0) { if(visit[p] == 0) { visit[p] = 1; temp += a[p]; if(temp == c) return 1; else if(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) { return 0; } } while(visit[p-1] == 0) { p--; if(p < 1) return 0; } visit[p-1] = 0; temp -= a[p-1]; } } return 0; } int main() { while(scanf(\"%d%d\ { memset(visit,0,sizeof(visit)); for(int i = 0; i < n; i++) scanf(\"%d\ if(GetRes()) printf(\"Yes\\n\"); else printf(\"No\\n\"); } return 0; } ———————————————————————————————————————————————————————— 最小重量机器设计问题 设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过cost的最小重量机器设计。 Input 每组测试数据第一行有3 个正整数n，m和cost。接下来的2n行，每行m个数。前n行是cij，后n行是wij。(1<=n,m<=20; 1<=cij <=100; 1<=wij<=100, 1<=cost<=40000) Output 分2行输出最小重量，以及每个部件的供应商。若找不到解决方案，则输出-1。 Sample Input 3 3 4 1 2 3 3 2 1 2 2 2 1 2 3 3 2 1 2 2 2 代码： #include using namespace std; const int len=30; const int maxWeight=4000; int n,m,cost; int w[len][len];//重量 int c[len][len];//价钱 int visit[len]; int path[len]; int minWeight = maxWeight; void findMinWeight(int current,int weight,int i) //当前策略的价钱和最小重量 { if(i >= n) { minWeight=weight; for(int j=0; j } for(int j=0; j if(current+c[i][j]<=cost && weight+w[i][j] current+=c[i][j]; weight+=w[i][j]; visit[i]=j+1; findMinWeight(current,weight,i+1); current-=c[i][j]; weight-=w[i][j]; } } } int main() { while(cin>>n>>m>>cost) { minWeight = maxWeight; int i,j; for(i=0; i<2*n; i++) { for(j=0; j if(i else cin>>w[i-n][j]; } } findMinWeight(0,0,0); if(minWeight == maxWeight) else { cout<<\"-1\"< if(i==0) cout< cout< } return 0; } —————————————————————————————————————————————————————— 排列宝石问题 问题描述： 现有n种不同形状的宝石，每种n颗，共n*n颗。同一种形状的n颗宝石分别具有n种不同的颜色c1, c2, ...,cn中的一种颜色。欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。 Input 每组测试数据为1个正整数n，0 输出宝石排列方案数 Sample Input 1 2 Sample Output 1 0 代码： #include #include using namespace std; const int len=10; int a[len][len]; int b[len][len]; int cc[len][len]; int dd[len][len]; int ee[len][len]; int n,cnt; void init() { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { a[i][j]=j; b[i][j]=j; cc[i][j]=0; } } } int ok(int r,int c,int k,int fla) { if(fla) { if(cc[a[r][c]][b[r][k]]) return 0; for(int i=1; i if(b[i][c]==b[r][k]) return 0; } } else { for(int i=1; i if(a[i][c]==a[r][k]) return 0; } } return 1; } void backtrack(int r,int c) { for(int i=c; i<=n; i++) { if(ok(r,c,i,0)) { swap(a[r][c],a[r][i]); for(int j=c; j<=n; j++) { if(ok(r,c,j,1)) { swap(b[r][c],b[r][j]); cc[a[r][c]][b[r][c]]=1; if(c==n) { if(r==n) { cnt++; } else backtrack(r+1,1); } else backtrack(r,c+1); cc[a[r][c]][b[r][c]]=0; swap(b[r][c],b[r][j]); } } swap(a[r][c],a[r][i]); } } } int main() { while(cin>>n) { cnt=0; init(); backtrack(1,1); cout< return 0; } —————————————————————————————————————————————————————— 多重幂计数问题 代码： #include using namespace std; __int64 f[40]; void inits() { int i,j; f[1]=1; for(i=2;i<=30;i++) { f[i]=0; for(j=1;j f[i]+=f[j]*f[i-j]; } } } bool run() { int n; if(!(cin>>n)) return false; printf(\"%I64d\\n\ return true; } int main() { inits(); while(run()); return 0; } 整数因子分解问题 大于1 的正整数n可以分解为：n=x1*x2*…*xm。例如，当n=12 时，共有8 种不同的分解式： 对于给定的正整数n，编程计算n共有多少种不同的分解式。 代码： #include using namespace std; int cnt; void dfs(int n) { for(int i=n-1;i>=2;i--) { if(n%i==0) { cnt++; dfs(n/i); } } } int main() { int n; while(cin>>n) { cnt=0; dfs(n); cout< return 0; } —————————————————————————————————————————————————————— 旅行规划问题 G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。 编程任务： 对于给定的d0,c,e,p,和n 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。 Input 每组测试数据的第1 行是d0,c,e,p,和n。接下来的n 行中每行2个数di 和pi。 Output 输出最小的旅行费用，精确到小数点后2 位。每个答案1行。 Sample Input 275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2 Sample Output 26.95 代码： #include #include #include using namespace std ; double f[10005][2]; double ff[10005][2]; bool run() { double d,c,e,p; int n,k; if(!(cin>>d>>c>>e>>p>>n)) return false; 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); double t,x; double y,a[2],b,q; for(i=1;i<=n;i++) { for(j=0;j t=ff[i][0]-ff[j][0]; x=f[j][0]*e; if(x>=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] b=(d-ff[j][0])/e; if((c-q) { if((ff[i][0]+b*e)>=ff[k][0]) { if(ff[k][1] b=(ff[k][0]-ff[i][0])/e; break; } } else break; } a[1]+=b*ff[j][1]; a[0]+=b; } if(a[0]==f[i][0]||f[i][1]==0) { if(a[1] f[i][0]=a[0]; f[i][1]=a[1]; } } else if(a[0]>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]; } } else if(a[0] if(a[1]+(f[1][0]-a[0])*ff[i][1] f[i][0]=a[0]; f[i][1]=a[1]; } } } } if(f[n][1]==0) { cout<<\"No Solution\\n\"; } else printf(\"%.2lf\\n\ return true; } int main() { while(run()); return 0; } —————————————————————————————————————————————————————— 多处最优服务次序问题 问题描述： 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1<=ti<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小? 平均等待时间是n个顾客等待服务时间的总和除以n。 代码： #include #include using namespace std; const int lenn=10000; const int lens=500; int n,s; int a[lenn]; int wait[lens]; int find() { int minTime=wait[0]; int pos=0; for(int i=1; i if(minTime>wait[i]) { minTime=wait[i]; pos=i; } } return pos; } int main() { while(cin>>n>>s) { int i; for(i=0; i cin>>a[i]; } sort(a,a+n); memset(wait,0,sizeof(wait)); double sum=0; for(i=0; i int t=find(); wait[t]+=a[i]; sum+=wait[t]; } double res=sum/n; printf(\"%.2f\\n\ } return 0; } —————————————————————————————————————————————————————— 可重复最优分解问题 问题描述： 设n是一个正整数。现在要求将n分解为若干个自然数的和，且使这些自然数的乘积最大。 编程任务： 对于给定的正整数n，编程计算最优分解方案。 Input 每组测试数据只有一个正整数n(1<=n<=10000)。 Output 输出最大乘积，每个答案一行。（提示：可能是一个非常大的整数！） Sample Input 10 Sample Output 36 代码： #include #include #include using namespace std; char res[10001]; int i, carry, len = 1; void mutiply(int n) { carry = 0; char *h = res; for (i = 0; i < len; i++) { *h = *h * n + carry; carry = *h / 10; *h %= 10; h++; } if (carry != 0) { *h = carry; len++; } } void f(int n) { int n3, n2, i; if (n %2 == 0) { n3 = n / 6 * 2; n2 = n % 6 / 2; } else { n3 = (n - 3) / 6 * 2 + 1; n2 = (n - 3) % 6 / 2; } for (i = 1; i <= n3 / 2; i++) { mutiply(9); } if (n3 % 2 != 0) { if (n2 > 0) { mutiply(6); n2--; } else { mutiply(3); } } if (n2 > 0) { mutiply((int)pow(2.0,n2)); } } int main() { int n; res[0] = 1; while(scanf(\"%d\ { if (n <= 3) { printf(\"%d\\n\ continue; } res[0] = 1; len = 1; f(n); for (i = len - 1; i >= 0; i--) { printf(\"%d\ } printf(\"\\n\"); } return 0; } —————————————————————————————————————————————————————— 有重复元素的排列问题 问题描述： 设R={ r1, r2, ..., rn}是要进行排列的n个元素。其中元素r1, r2, ...,rn可能相同。试设计一个算法，计算出这n 个元素的所有不同排列数。 Input 每组测试数据首先是n(1<=n<=500)，接着是待排列的n个元素(小写字母)。 Output 输出排列总数。 Sample Input 4 aacc Sample Output 6 代码： #include #include #include using namespace std; const int len=510; int n,ans; char list[len]; int ok(int k,int i) { if(i>k) { for(int t=k; t if(list[t]==list[i]) return 0; } } return 1; } void findResult(int k) { if(k==n-1) { ans++; } else { for(int i=k; i if(ok(k,i)) { swap(list[k],list[i]); findResult(k+1); swap(list[k],list[i]); } } } } int main() { while(cin>>n) { ans=0; for(int i=0; i cin>>list[i]; } findResult(0); cout< return 0; } —————————————————————————————————————————————————————— 运动员最佳匹配问题 问题描述： 羽毛球队有男女运动员各n人。给定2个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。 Input 每组测试数据第一行有1个正整数n(1≤n≤20)。接下来的2n行，每行n个数。前n行是p矩阵，后n行是q矩阵。 Output 输出男女双方竞赛优势总和的最大值。 Sample Input 3 10 2 3 2 3 4 3 4 5 2 2 2 3 5 3 4 5 1 Sample Output 52 代码： #include using namespace std; int a[22]; int p[22][22]; int q[22][22]; int n; int sum=0; void swap(int &x,int &y) { int temp=x; x=y; y=temp; } void Backtrack(int t) { if(t>n) { int s=0; for(int j=0;j s+=p[j][a[j+1]-1]*q[a[j+1]-1][j]; } if(s>=sum) sum=s; } else { for(int i=t;i<=n;i++) { swap(a[i],a[t]); Backtrack(t+1); swap(a[i],a[t]); } } } int main() { int i,j; while(cin>>n) { for(i=0;i<=n;i++) a[i]=i; for(i=0;i for(j=0;j cin>>p[i][j]; } } for(i=0;i for(j=0;j cin>>q[i][j]; } } Backtrack(1); cout< return 0; } —————————————————————————————————————————————————————— 半数集问题 给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n)； (2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。 编程任务： 对于给定的自然数n，编程计算半数集set(n)中的元素个数。 代码： #include #include using namespace std; int a[1111]; int main() { int i,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< return 0; } —————————————————————————————————————————————————————— 编辑距离问题 编辑距离问题 设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。 编程任务： 对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。 Input 每组测试数据分两行，第一行是字符串A，第二行是字符串B。(长度最大110) Output 输出距离d(A,B)，每个答案一行。 Sample Input fxpimu xwrs Sample Output 5 代码： #include #include using namespace std; const int len=112; int d[len]; string a,b; int getMin(int x,int y,int z) { if(x<=y && x<=z) return x; else if(y<=x && y<=z) return y; else if(z<=x && z<=y) return z; } int main() { while(cin>>a>>b) { int m=a.size(); int n=b.size(); int i,j; for(i=1; i<=n; i++) d[i]=i; for(i=1; i<=m; i++) { int y=i-1; for(j=1; j<=n; j++) { int x=y; y=d[j]; int z = j>1 ? d[j-1]:i; int del = a[i-1]==b[j-1] ? 0:1; d[j]=getMin(x+del,y+1,z+1); } } cout< return 0; } 因篇幅问题不能全部显示，请点此查看更多更全内容