题目: P1018[乘积最大]
前言:
这题的正解理论上说是 DP, 可是由于民间数据太水, 用暴力过并不难
整体思路:
利用一个 b 数组标记每一位之间是否分割(1 位分割, 0 为连接).
利用 STL 里的 next_permutation 求出 b 的各种排列(即暴力枚举每种情况).
由于本题数据规模大, 所以要使用高精度计算每种分割的最后结果, 并找出最大.
next_permutation 函数:
即 STL 里的求全排列函数, 所求的数组必须是升序, 否则将无法求出全部的排列方式(这和它生成群排列的方式有关),next_permutation 正常和 sort 一样, 有 2 个参数, 分别是数组的首地址和尾地址, 并返回一个 bool 量, 即能否求出下一个全排列, 可以的话返回 true, 并将指定数组变为下一个排列方式, 如 1 2 3 的下一个排列方式就是 1 3 2.
上代码:
- #include<algorithm> // 使用 next_permutation 需要调用的头文件
- #include<cstdio> //c 语言读入输出
- #include<cstring> // 处理高精度字符串时需要用到
- using namespace std;
- struct BigN{ // 高精度 (即大整数) 运算
- int num[1001]={0},len;
- BigN(char s[]) // 构造函数, 用于给新定义的大整数赋值
- {
- len=strlen(s);
- for(int i=len-1;i>=0;i--)
- num[i]=s[len-i-1]-'0';
- }
- void clean() // 用于清零
- {
- memset(num,0,sizeof(num));
- }
- void f(int n) // 将一个普通整数压到大整数的开头, 这个在后面分割每一位时会用到
- {
- for(int i=len;i>0;i--)
- num[i]=num[i-1];
- len++;
- num[0]=n;
- }
- void cheng(BigN n)// 高精度乘法, 这里就不过多解释了, 有疑问可以前往 P1303 了解更多
- {
- BigN c("0");
- int s=0,g=0;
- for(int i=0;i<=len;i++)
- for(int j=0;j<=n.len;j++)
- {
- int w=i+j;
- s=num[i]*n.num[j];
- c.num[w]+=s%10;
- c.num[w+1]+=s/10+c.num[w]/10;
- c.num[w]%=10;
- }
- c.len=len+n.len;
- while(c.num[c.len]==0&&c.len>=0)c.len--;
- fz(c);
- }
- void fz(BigN n) // 将一个大整数赋值给例外一个大整数, 相当于'='
- {
- len=n.len;
- for(int i=0;i<=n.len;i++)
- num[i]=n.num[i];
- }
- bool bj(BigN n) // 判断两个大整数的大小, 用于找出最大结果
- {
- if(len>n.len)
- return 1;
- else if(len<n.len)
- return 0;
- else
- {
- for(int i=len;i>=0;i--)
- if(num[i]<n.num[i])
- return 0;
- else if(num[i]>n.num[i])
- return 1;
- return -1;
- }
- }
- void out() // 输出
- {
- for(int i=len;i>=0;i--)
- printf("%d",num[i]);
- }
- };
- int n,k,sum[55],b[55],i,j; // 常规定义, 不多做解释
- BigN mmax("0");
- int main()
- {
- char s[101]; //s 用于读入一个大整数
- scanf("%d%d%s",&n,&k,&s);
- for(i=0;i<strlen(s);i++) // 在 sum 中备份一份原数
- sum[i]=s[i]-'0';
- for(i=n-2;i>=(n-k)-1;i--) // 将 b 数组中的后 k 个数赋 1, 因为使用 next_permutation 需要让数组升序, 否则可能无法找出所有排列方式
- b[i]=1;
- do{
- BigN temp("0"),all("1");//temp 用于存放分割后的每一节, all 用于计算每种排列方式的结果
- i=0;
- while(i<n)// 分割
- {
- if(i!=0)
- if(b[i-1]==1)// 如果 b[i-1]为 1, 那么就要在这一位加上一个乘号, 即将原数分割
- all.cheng(temp),temp.clean();// 总数乘上分割后的每一位, 并将 temp 清空, 用于储存下一节.
- temp.f(sum[i]),i++; // 将原数的下一位压到 temp 的最前面
- }
- all.cheng(temp);// 由于 temp 还没有乘 all 就退出循环, 所以要再乘一次
- if(mmax.bj(all)==0)// 如果这种排列顺序的结果大于之前最大的结果, 刷新最大结果
- mmax.fz(all);
- }while(next_permutation(b,b+n-1));// 调用 next_permutation
- mmax.out();// 输出
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3280751.html