SCAU 算法设计与分析 OJ复习

8594 有重复元素的排列问题（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:1610 通过次数:656

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
设集合R={r1,r2,…,rn}是要进行排列的n个元素，其中r1,r2,…,rn可能相同。
试着设计一个算法，列出R的所有不同排列。
即，给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。

输入格式
第1行是元素个数n，1<=n<=15。接下来的1行是待排列的n个元素，元素中间不要加空格。

输出格式
程序运行结束时，将计算输出n个元素的所有不同排列。最后1行中的数是排列总数。

（说明：
此题，所有计算出的排列原本是无所谓顺序的。但为了容易评判，输出结果必须唯一！
现做约定：所有排列的输出顺序如课本例2-4的程序段的输出顺序，区别仅是这道题是含
重复元素。）

输入样例
4
aacc

输出样例
aacc
acac
acca
caac
caca
ccaa
6

提示

课本上有“递归”实现无重复元素全排列的源程序。
稍加修改即可满足此题要求。

在递归产生全排列的那段程序开始之前，
加一个判断：判断第i个元素是否在list[k,i-1]中出现过。
PermExcludeSame(char list[], int k, int m)
{
…
for (int i=k; i<=m; i++)
{
if (Findsame(list,k,i))//判断第i个元素是否在list[k,i－1]中出现过
continue;
Swap (list[k], list[i]);
PermExcludeSame(list, k+1, m);
Swap (list[k], list[i]);
}
}

#include using namespace std;int countAll = 0;// 字符串匹配
bool Findsame(char list[], int k, int m){// list[m]是否有在list[k, m-1]出现过for (int i = k; i < m; i++) {if (list[m] == list[i]) {// 出现了return true;}}return false;
}
// 全排列，递归
void Perm(char list[], int k, int m){if (k == m) {// 输出排列for (int i = 0; i <= m; i++) {cout << list[i];}countAll++;// 排列数+1cout << endl;}else{for (int i = k; i <= m; i++) {if (Findsame(list, k, i)) {continue;//去除已出现过的排列}swap(list[k], list[i]);Perm(list, k + 1, m);// 递归swap(list[k], list[i]);}}
}
int main()
{int n;char list[20];cin >> n;cin >> list;Perm(list, 0, n - 1);cout << countAll;cout << endl;return 0;
}

9718 整数因子分解（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
大于1的正整数 n 都可以分解为 n = x1 * x2 * … * xm， 每个xi为大于1的因子，即1

例如：当n=12时，共有8种不同的分解式：
12 = 12
12 = 62
12 = 43
12 = 34
12 = 322
12 = 26
12 = 232
12 = 223

对于给定正整数n，计算n共有多少种不同的分解式。

输入格式
第一行一个正整数n （1<=n<=1000000）

输出格式
不同的分解式数目

输入样例
12

输出样例
8

提示

此题因子讲顺序的.第一个因子可能是2~n之间的数.
比如对12而言,第一个因子可能是2,3,4,6,12.

将第一个因子为2的分解个数,加上第一个因子为3的分解个数,…,直至加到第一个因子为12的分解个数.

而第一个因子为2的分解个数又是多少呢?是对6去做因子分解的个数(因为12/2=6),递归求解!

可用“递归”和“备忘录方法”两种方法分别求解，并测试一下效率。

递归实现整数因子分解的计数。假设对正整数n的因子分解计数为solve1(n)。
1）当n=1时，计数加1。
2）当n>1时，对n的每个因子i，计算solve1(n/i)。
void solve1 (int n)
{
if (n==1) total++; //total为全局变量，有初始化
else for (int i=2; i<=n; i++)
if (n%i ==0)
solve1(n/i);
}

或者另外一种实现方式：
递归算法同，但这样实现更容易理解：
int solve2(int n)
{
int num=0;

if(n==1) return 1;for(int i=2; i<=n; i++)if(n%i == 0) num+=solve2(n/i);return num;

}

#include 
#include 
#include using namespace std;int total=0;void solve1 (int n)
{if (n==1) total++;  //total为全局变量，有初始化else for (int i=2; i<=n; i++)if (n%i ==0)solve1(n/i);
}int main()
{int n;scanf("%d",&n);solve1(n);printf("%d",total);return 0;
}

17082 两个有序数序列中找第k小（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
已知两个已经排好序（非减序）的序列X和Y，其中X的长度为m，Y长度为n，
现在请你用分治算法，找出X和Y的第k小的数，算法时间复杂度为O(max{logm, logn})。

此题请勿采用将序列X和Y合并找第k小的O(m+n)的一般方法，要充分利用X和Y已经排好序的这一特性。

输入格式
第一行有三个数，分别是长度m、长度n和k，中间空格相连（1<=m,n<=100000; 1<=k<=m+n）。
第二行m个数分别是非减序的序列X。第三行n个数分别是非减序的序列Y。

输出格式
序列X和Y的第k小的数。

输入样例
5 6 7
1 8 12 12 21
4 12 20 22 26 31

输出样例
20

#include 
#include 
#include using namespace std;int fun(int x[],int y[],int xbeg,int xend,int ybeg,int yend,int k)
{//X序列为空时，直接返回Y序列的第k小元素。if (xbeg > xend) return y[ybeg + k - 1];//Y序列为空时，直接返回X序列的第k小元素。if (ybeg > yend) return x[xbeg + k - 1];int xmid = (xbeg+xend)/2;//x的中间位置int ymid = (ybeg+yend)/2;//y的中间位置int halfLen = xmid-xbeg+ymid-ybeg+2;//x和y的左段元素个数之和if (x[xmid]<y[ymid]){if (k<halfLen){//此时第k大的元素一定小于Y[yMid]这个元素，所以要mid-1//此时只需递归的对X序列+Y序列的前半段，去搜索第k小的数。fun(x,y,xbeg,xend,ybeg,ymid-1,k);}else{//此时第k大的元素一定大于X[xMid]这个元素，所以要mid+1//此时只需递归的对X序列的后半段+Y序列,去搜索第 k-(xMid-xBeg+1）小的数。fun(x,y,xmid+1,xend,ybeg,yend,k-(xmid-xbeg+1));}}else{if(k<halfLen){//此时第k大的元素一定小于X[xMid]这个元素，mid-1//此时只需递归的对X序列的前半段+Y序列，去搜索第k小的数。fun(x,y,xbeg,xmid-1,ybeg,yend,k);}else{//此时第k大的元素一定大于Y[yMid]这个元素，mid+1//此时只需递归的对X序列+Y序列的后半段，去搜索第 k-(yMid-yBeg+1）小的数。fun(x,y,xbeg,xend,ymid+1,yend,k-(ymid-ybeg+1));}}
}int main()
{int m,n,k;scanf("%d %d %d",&m,&n,&k);int x[m],y[n];int halfLen = m+n;for (int i=0;i<m;i++){scanf("%d",&x[i]);}for (int i=0;i<n;i++){scanf("%d",&y[i]);}printf("%d",fun(x,y,0,m-1,0,n-1,k));return 0;
}

10303 数字三角（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:117 通过次数:56

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
问题描述：给定一个由n行数字组成的数字三角形，如下图所示。试用动态规划算法，计算出从三角
顶部至底部的一条路径，使得该路径经过的数字总和最大。

注意每个数字只能走向下一行左边或右边的数字，而不能跳跃的走。

     73   8
8   1   0

2 7 4 4
4 5 2 6 5

输入格式
第一行是数字三角的行数n，1<=n<=100。接下来n行是数字三角各行中的数字，所有数字在0~99之间。

输出格式
输出两行，第一行是计算出的最大路径的和值，第二行是该路径上的数字。若有多条路径，靠右的路径
优先（即仅仅输出靠右的路径即可，无需多条路径都输出）。

如：
Input:
5
7
3 8
8 1 6
2 7 4 4
4 5 2 4 5
有两条路径：7-3-8-7-5和7-8-6-4-5都为30，由于后者靠右，因此仅输出后者。
Output:
30
7 8 6 4 5

输入样例
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例
30
7 3 8 7 5

#include
#define N 101
int a[N][N],m[N][N];int max(int a,int b){return a>b?a:b;
}void MaxRoad(int n){for(int j=1;j<=n;j++)m[n][j]=a[n][j];for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){m[i][j]=max(m[i+1][j],m[i+1][j+1])+a[i][j];}}
}void Back(int n){int j=1;//j不变表示向下走，j+1表示往右走printf("%d ",a[1][1]);for(int i=2;i<=n;i++){if(m[i][j]<=m[i][j+1]){printf("%d ",a[i][j+1]);j=j+1;}else{printf("%d ",a[i][j]);}}
}int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){scanf("%d",&a[i][j]);}}MaxRoad(n);printf("%d\n",m[1][1]);Back(n);return 0;
}

8596 最长上升子序列（优先做）

时间限制:300MS 代码长度限制:10KB
提交次数:255 通过次数:118

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
当元素 ai1 < ai2 < … < aiK. 就说这个序列是有序上升的。

给定序列(a1, a2, …, aN)，存在许多这样的子序列(ai1, ai2, …, aiK)，
其中1 <= i1 < i2 < … < iK <= N.
也就是说，子序列是原序列允许挑选若干不连续的元素形成的序列。

举个例子，序列 (1, 7, 3, 5, 9, 4, 8) 就有许多个上上子序列，比如(1, 7), (3, 4, 8) 等。
所有这些上升子序列中最长的长度为4，比如 (1, 3, 5, 8).

你来编程实现，当给定一个初始序列，寻找这个序列的最长上升子序列。

输入格式
此例包含多个测试cases（少于100组test cases）。
每一组test case包含2行。
第一行是这组case的序列长度 N。（N的范围0~10000）
第二行包含 N个整数的一个序列，用空格间隔这N个整数， 1 <= N <= 10000。

当N为0时，表示测试结束。

输出格式
输出必须对每个test case，都有一个整数结果，表示这组case的最长上升子序列的长度。

输入样例
7
1 7 3 5 9 4 8
6
1 8 3 6 5 9
5
1 2 3 4 5
0

输出样例
4
4
5

提示

一，对输入字符串的处理

注意：这道题和其他题的输入输出不同,这题是接收多组数据而非单组,以0来判别结束。
大家在接受数据的时候，不要用(c=getchar())!=’\n’诸如此类一个字符一个字符接受，
然后判断是否是回车符号来结束一行的输入，这样的方式在你本机运行不会有问题，
但OJ系统中会有错误，无法输出结果，因为测试平台行末并非’\n’字符。
这里接受数据用scanf的%d或%s，或cin等，会自动判别结束字符的，你就不要在你程序
里专门去判别或吸收回车字符。

对于最后一组数据输入为0表示结束，只要判断接受的第一个字符是否为0且字符串长度
为1就结束，无须去处理回车字符。

输入的序列可以用整型数组或字符串数组保存。

二，算法的动态规划思想

考虑采用动态规划算法，针对每个元素，以该元素结尾的最长有序子序列作为子问题，
计算出每个子问题的最大长度用“表”记录下来。先写出递推关系式再编程实现。

设f(i)表示：从左向右扫描过来直到以a[i]元素结尾的序列，可获得的最长上升
子序列的长度，且最长上升子序列包含a[i]元素（1<=i<=n）。

（这里大家思考一下，为何要这样假设子问题和子问题最优解f(i)？
有同学问：为何最长上升子序列要包含a[i]元素（1<=i<=n）？
因为你所设的子问题要和更下一级子问题关联起来。如果长度为i序列的最长上升
子序列中没有规定包含a[i]元素，那如何和其前缀的最长上升子序列问题关联起来
呢？因为你没法确认你前缀的最长上升子序列最后一个字符在哪里？上升子序列的
边界在哪不知道的话，很难和更小规模的子问题联系起来，显然是比较麻烦的。）

f(i)是从f(1),f(2), ……到f(i-1)中找最大的一个值，再加1，或者就是1。
这主要得看a[i]这个元素能否加入到之前已经获得的最长上升子序列当中去，
如果能加入，是之前已获得的最长上升子序列长度加1；
如果不能加入，就开始一个新的上升子序列，长度为1。
最后，所要求的整个序列的最长上升子序列长度为 max{ f(i): 1<=i<=n }

f(i)的递推公式如下：
（1）f(i) = 1 当i=1;
（2）f(i) = max{f(j)+1} 当i>1, 对某个前面的j(1<=j （3）f(i) = 1 当i>1, 对任意j(1<=j=a[i]

例子，对于序列：4 2 6 3 1 5 2
i = 1 2 3 4 5 6 7
a[i] = 4 2 6 3 1 5 2
f(i) = 1 1 2 2 1 3 2

这里max{f(i)}=3为原问题所求的最长上升子序列的长度。

效率分析：
f(i)的计算不超过O(n)，因此，整个算法为O(n^2)。

#include 
#include 
#include 
#includeusing namespace std;int main(){while(true){int n;cin>>n;if(n==0){break;}int a[n];for (int i = 0; i < n; ++i) {cin>>a[i];}int f[n];for(int i=0;i<n;i++) {if (i == 0) {f[i] = 1;}else {int t = 1;for (int j = 0; j < i; j++) {if (a[j] < a[i] && t < f[j] + 1) {t = f[j] + 1;}}f[i] = t;}}sort(f,f+n);cout<<f[n-1]<<endl;}}

8601 最大长方体问题（优先做）

时间限制:800MS 代码长度限制:10KB
提交次数:950 通过次数:383

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
一个长,宽,高分别是m,n,p的长方体被分割成mnp个小立方体。每个小立方体内含一个整数。

试着设计一个算法，计算所给长方体的最大子长方体。子长方体的大小由它内部所含所有整数之和确定。

约定：当该长方体所有元素均为负数时，输出的最大子长方体为0。

输入格式
第一行3个正整数m,n,p，其中 1<=m,n,p<=50

接下来的m*n行中每行p个整数，表示小立方体中的数。

输出格式
第一行中的数是计算出的最大子长方体的大小。

输入样例
3 3 3

0 -1 2

1 2 2

1 1 -2

-2 -1 -1

-3 3 -2

-2 -3 1

-2 3 3

0 1 3

2 1 -3

输出样例
14

提示

这里，很多同学不会动态申请数组，还和静态定义数组一样写成如下：
int n;
n=10000; //或cin>>n;
int c[n];

最好不要这样写，可能会出错的啊，且不报错，可以运行，但结果可能会不对。
其他的题目如果你想“动态申请数组空间”都同理如下这样来表达。

//一维数组动态申请，c数组大小为： n
int *c=new int[n];

//二维数组动态申请，b数组大小为： n*p
int *b=new int[n];
for(int i=0;i b[i]=new int[p];

//三维数组动态申请, a数组大小为： mnp:
int ***a=new int **[m];
for(i=0;i {
a[i]=new int *[n];
for(j=0;j a[i][j]=new int [p];
}

另外，当不再需要一个动态分配的多维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分
配的空间。然后释放为行指针分配的空间。

//一维空间释放：
delete []c;
c=0; //可在释放空间后将c置为0，以防继续访问已被释放的空间。这句可以不要。

//二维空间释放：
for (int i=0;i delete []b[i];
delete []b;
b=0; //可在释放空间后将b置为0，以防继续访问已被释放的空间。这句可以不要。

//三维空间释放：
for (int i=0;i {
for(j=0;j delete []a[i][j];
delete []a[i];
}
delete []a;
a=0; //可在释放空间后将a置为0，以防继续访问已被释放的空间。这句可以不要。
数据输入格式为：

for (i=0;i for (j=0;j for (k=0;k cin >> a[i][j][k];

此题思路：
1，先编写一维的“最大字段和”的解法。
2，基于“最大字段和”，编写二维的“最大子矩阵和”的解法。
3，基于“最大子矩阵和”，编写三维的“最大子长方体和”的解法。
三维的最大子长方体和求解过程：对原三维长方体，枚举在某个方向上切各种厚薄的片（如切吐司面包一样，切一段），
这个各种厚薄的片，得用两重循环来枚举（0<= i

#include
using namespace std;
int MaxSum(int p, int* a);
int MaxSum2(int n, int p, int** a);
int MaxSum3(int m, int n, int p, int*** a);int main(){int m, n, p, ***a;cin >> m >> n >> p;a = new int**[m + 1];for (int i = 1; i <= m; i++)a[i] = new int*[n + 1];for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)a[i][j] = new int[p + 1];for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)for (int k = 1; k <= p; k++)cin >> a[i][j][k];cout << MaxSum3(m, n, p, a);for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)delete[] a[i][j];for (int i = 1; i <= m; i++)delete[] a[i];delete[] a;return 0;
}int MaxSum(int p, int* a) {int sum = 0, b = 0;for (int i = 1; i <= p; i++) {if (b > 0)b += a[i];elseb = a[i];if (b > sum)sum = b;}return sum;
}int MaxSum2(int n, int p, int** a) {int sum = 0;int *b = new int[p + 1];for (int i = 1; i <= n; i++) {for (int k = 1; k <= p; k++)b[k] = 0;for (int j = i; j <= n; j++) {//i,j 决定MaxSum被调用的次数,n = 3, 则3 + 2 + 1 = 6次for (int k = 1; k <= p; k++)b[k] += a[j][k];/*for (int k = 1; k <= p; k++)cout << "i " << i << " j " << j << " " << "[" <<  b[k] << "] ";cout << endl;*/int max = MaxSum(p, b);if (max > sum) {sum = max;//cout << "i " << i << " j " << j << " " << "sum " << sum << endl;}}//cout << endl;}delete[] b;return sum;
}int MaxSum3(int m, int n, int p, int*** a) {int sum = 0;int** c = new int*[n + 1];for (int i = 1; i <= n; i++)c[i] = new int[p + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++)for (int k = 1; k <= p; k++)c[j][k] = 0;for (int l = i; l <= m; l++) {//i,l 决定MaxSum2被调用的次数, 如m = 3, 则3 + 2 + 1 = 6for (int j = 1; j <= n; j++)for (int k = 1; k <= p; k++)c[j][k] += a[l][j][k];int max = MaxSum2(n, p, c);//cout << endl;if (max > sum)sum = max;}}for (int i = 1; i <= n; i++)delete[] c[i];delete[] c;return sum;
}

11077 最长公共子字符串（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
求两个输入序列的最长的公共子字符串的长度。子字符串中的所有字符在源字符串中必须相邻。

如字符串：21232523311324和字符串312123223445，他们的最长公共子字符串为21232，长度为5。

输入格式
两行，第一行为第一个字符串X，第二行为第二个字符串Y，字符串不含空格并以回车标示结束。X和Y的串长都
不超过10000。

输出格式
两行，第一行为最长的公共子字符串的长度，第二行输出一个最长的公共子字符串。

说明：
(1)若最长的公共子字符串有多个，请输出在源字符串X中靠左的那个。
(2)若最长公共子字符串的长度为0，请输出空串(一个换行符)。

如输入：
21232523311324
152341231
由于523和123都是最长的公共子字符串，但123在源串X中更靠左，因此输出：
3
123

输入样例
21232523311324
312123223445

输出样例
5
21232

提示

一，对输入字符串的处理
大家在接受数据的时候，不要用(c=getchar())!=’\n’诸如此类一个字符一个字符接受，然后判断是否是回车
符号来结束一行的输入，这样的方式在你本机运行不会有问题，但OJ系统中会有错误，无法输出结果，因为
测试平台行末并非’\n’字符。这里接受数据用scanf的%s，或cin等，会自动判别结束字符的，你就不要在你
程序里专门去判别或吸收回车字符。

二，递推公式
此题和书上3.3节"最长公共子序列"描述是不同的，子序列可由不连续字符组成，但子字符串是连续的。
此题更加简单!

假设求字符串str1,str2的最长公共子串的长度.
定义f(m,n)： 分别以str1[m],str2[n]结尾的最长连续公共子串的长度，
其中字符串末尾的str1[m]和str2[n]包含在最长公共子串中，即为最长公共子串的最末元素。

（这里大家思考一下，为何要这样假设子问题和子问题最优解f(m,n)？
因为子串是连续的，更大规模问题和下一级更小规模的子问题要能联系起来，而且这种联系还要越简单越好，
只有规定原先两个串的最末元素包含在最长公共子串中，这样就能联系上两个串的前缀部分（都去掉末个元
素）的最长公共子串问题。）

而对于f(m+1,n+1) 有：

1. f(m+1,n+1) = 0, if str1[m+1] != str2[n+1]
2. f(m+1,n+1) = f(m,n) + 1, if str1[m+1] == str2[n+1]
3. 另外边界情况，f(0,j)=0(j>=0), f(j,0)=0(j>=0)

而此题所求的最长公共字符串的长度即为f(m,n)整个二维数组中的最大值，注意不是填充的最后一个元素。
也不是最后一行元素的最大值，而是整个二位数组的最大值。思考一下为什么呢？

至于如何优先输出在源串X靠左的公共子串，大家自行思考。
这也容易，在你比较产生数组最大值maxlen时，就同步记录下那时在x数组中的下标位置，比如此位置叫endindex_x。
最后用这个位置在X序列中输出从X[endindex_x - maxlen + 1]元素一直到X[endindex_x]元素即可。

#include
#include
#define MAXN 100010
char a[MAXN], b[MAXN];
int p[MAXN], q[MAXN];int main()
{
//    freopen("input.txt", "r", stdin);int i, j, len_a, len_b, sum, x, y;scanf("%s%s", a, b);len_a = strlen(a);len_b = strlen(b);memset(p, 0, sizeof(p));memset(q, 0, sizeof(q));sum = 0;for(i=0; i<len_a; ++i){memcpy(q, p, sizeof(int)*len_b);memset(p, 0, sizeof(p));for(j=0; j<len_b; ++j){if(a[i] == b[j]){if(j == 0) p[j] = 1;else p[j] = q[j-1]+1;if(sum < p[j]){x = j;sum = p[j];}}}}printf("%d\n", sum);a[sum--] = '\0';for( ; sum>=0; --sum, --x)a[sum] = b[x];printf("%s\n", a);return 0;
}

11079 可以移动的石子合并（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
有n堆石子形成一行(a1,a2,…,an，ai为第i堆石子个数)，现要将石子合并成一堆，规定每次可
选择至少2堆最多k堆移出然后合并，每次合并的分值为新堆的石子数。

若干次合并后，石子最后肯定被合并为一堆，得分为每次合并的分值之和。

现在求解将这n堆石子合并成一堆的最低得分和最高得分。

输入格式
两行。第一行n和k。
第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=200，2<=k<=n。

输出格式
仅一行，为石子合并的最低得分和最高得分，中间空格相连。

输入样例
7 3
45 13 12 16 9 5 22

输出样例
199 593

提示

此题贪心算法求解.
给这题标记标签"dp"方法是同学所为,并非老师标注.动规不是不可以,但有更好更快的贪心解法的.

如7堆石头，每次可选择最少2堆最多3堆合并，可以如下这样合并：
第1次合并：45+22=67
第2次合并：67+16=83
第3次合并：83+13=96
第4次合并：96+12=108
第5次合并：108+9=117
第6次合并：117+5=122
合并的总分值：67+83+96+108+117+122=593，593已是最大分值。

也可以这样合并：
第1次合并：5+9+12=26
第2次合并：13+16+22=51
第3次合并：45+51+26=122
合并的总分值：26+51+122=199，199已是最小分值。

因此此题贪心的方法如下：

（1）保证每次选两堆最多的，合并直至只剩一堆为止，能获得最大得分；
这个和huffman树构造是相同的，不再详述！

（2）保证每次选k堆最少的，合并直至只剩一堆为止，能获得最小得分。
这个是多元huffman树的构造。要注意的是：在合并之前，若n%(k-1)!=1，说明合并到最后一轮时，
剩下不是k堆（而是比k堆少），这样算的并不是最小得分，而必须在合并之前添加若干个为0的虚拟
堆，目的为凑成的堆数保证每次都能有k堆合并（包括最后一次）最后合并为1堆。

因此，在合并前作如下处理：

//假设石头每堆个数放于stone[1]~stone[n],且stone[n]之后最多k-1个数组单元为可写;
while (n % (k - 1) != 1)
{
n++;
stone[n]=0;
}

#include 
#include 
using namespace std;int a[201];
int b[201];
int MaxSum=0;
int MinSum=0;//最少2堆，最多k堆
void Pmax(int n){//n始终指向最后一个数的下一个位置//m失踪指向下一堆的最后一个数的下一个位置if(n==1)return; //只剩下a[0] 即计算完毕else if(n>=1){int m= n-1;b[m-1] += b[m];MaxSum +=b[m-1];sort(b,b+m);Pmax(m);}}void Pmin(int m,int n,int k){if(m==n)return;else if(n-m>=k-1){for(int i=0;i<=k-2;i++){a[m+k-1] += a[m+i];}m += k-1;MinSum +=a[m];sort(a+m,a+n);Pmin(m,n,k);}
}int main()
{int n,k;cin>>n>>k;for(int i=0;i<n;i++){cin>>a[i];b[i]=a[i];}sort(b,b+n);Pmax(n);//用数组b//只有最后一组也是k个才是最小的情况while((n%(k-1))!=1){   n+=1;a[n]=0;}sort(a,a+n);Pmin(0,n-1,k);//用数组acout<<MinSum<<" "<<MaxSum;return 0;
}

8595 钱币组合的问题（优先做）
时间限制:300MS 代码长度限制:10KB
提交次数:897 通过次数:398

题型: 编程题 语言: G++;GCC;VC;JAVA

Description
设有n种不同的钱币各若干，可用这n种钱币产生许多不同的面值。
如给定面值7分，有1分3张，2分3张，5分1张，能组成给定面值7分的方法有如下4种：
3个1分+2个2分； 5个；
1个1分+3个2分； 4个；
2个1分+1个5分； 3个；
1个2分+1个5分； 2个。

上面4种方案的最少张数为2个。

你的编程任务：给定面值m，和n种不同面值钱币及其张数，
（1） 求给定面值m能有多少种不同的构成方法数。
（2） 求给定面值m最少要多少张。

输入格式
第1行有1个正整数n(1<=n<=50)，表示有n种不同的钱币。
第2行有n个数，分别表示每种钱币的面值v[1]…vn。
第3行有n个数，分别表示每种钱币的张数k[1]…kn。
第4行有1个数，表示给定的面值m (1<=m<=20000)。

输出格式
两行：
第一行：计算出给定面值的不同的方法种数。若无法给出找钱方案，返回0数值。
第二行：计算出给定面值所需的最少张数。若无法给出找钱方案，返回“no possible”(无大写，无标点)。

输入样例
3
1 2 5
3 3 1
7

输出样例
4
2

提示

（1）给定面值m的不同方法种数

给定的总面值m，n种钱币，每种钱币面值v[1…n],每种钱币的张数k[1…n]，
用一个二维数组d[i][1…m]记录用前i种钱币组成1…m面值产生的方法数。1<=i<=n。
初始，该数组全清零，然后逐个加入第i种面值的钱币（1<=i<=n），并修改影响到数组d的方法数。

设d[i,j]:表示前i种钱币组成面值j分的方法数，1<=i<=n,0<=j<=m。(j>=0才有意义，若j<0,可视为d[i,j]=0)
d[i,0] = 1, if 1<=i<=n
d[1,j] = 1, if j%v[1]=0 && j/v[1]<=k[1];
d[1,j] = 0, if j%v[1]!=0 || j/v[1]>k[1] || j<0;

if i>1 && j1 && v[i]<=j<2*v[i]
d[i,j] = d[i-1,j] + d[i-1,j-v[i]]

if i>1 && 2v[i]<=j<3v[i]
d[i,j] = d[i-1,j] + d[i-1,j-v[i]] + d[i-1,j-2*v[i]]

…

if i>1 && k[i]v[i]<=j<=m
d[i,j] = d[i-1,j] + d[i-1,j-1v[i]] + d[i-1,j-2*v[i]] + … + d[i-1,j-k[i]*v[i]]
//这里要注意，要保证 j-k[i]*v[i]>=0 才有意义，对可能的越界（无论是左边越界还是右边越界），都要仔细审查。

最后d[n,m]为原问题所求。

当然由于这里的d数组d[i,j]只与d[i-1,…]有关，也完全可以用一维数组d[1…m]来实现。

（2）求给定面值m最少要多少张

假设c[i][j]表示：选择前i种面值的钱，凑成面值j的最少张数，这里1<=i<=n, 0<=j<=m。
c[i][j]的递归关系如下：

令：t = min{ (int)(j/v[i]), k[i] }，表示第i种钱币最多加入的张数。
c[i][j] = min{ p+c[i-1][j-pv[i]] | p from 0 to t }，这里p表示第i种币值选入的张数，
t表示第i种币值最多选入的张数。
//这里要注意，要保证 j-pv[i]>=0 才有意义，对可能的越界（无论是左边越界还是右边越界），都要仔细审查。

初始条件：
c[i][0]=0, 1<=i<=n
c[1][j]=int(j/v[1]), if j%v[1]==0 && j/v[1]<=k[1]
c[1][j]=MAXINT, if j%v[1]!=0 || j/v[1]>k[1]
//此处MAXINT为自定义的无穷大的数，表示没法放。

最后返回c[n][m]，若c[n][m]为MAXINT，则无法找到找钱的方案。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！