原文:https://www.luogu.org/problemnew/solution/P1018?page=7

题目:P1018【乘积最大】


前言:

  • 这题的正解理论上说是DP,可是由于民间数据太水,用暴力过并不难

整体思路:

  1. 利用一个b数组标记每一位之间是否分割(1位分割,0为连接)。
  2. 利用STL里的 next_permutation 求出b的各种排列(即暴力枚举每种情况)。
  3. 由于本题数据规模大,所以要使用高精度计算每种分割的最后结果,并找出最大。

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[]={},len;
BigN(char s[]) //构造函数,用于给新定义的大整数赋值
{
len=strlen(s);
for(int i=len-;i>=;i--)
num[i]=s[len-i-]-'';
}
void clean() //用于清零
{
memset(num,,sizeof(num));
}
void f(int n) //将一个普通整数压到大整数的开头,这个在后面分割每一位时会用到
{
for(int i=len;i>;i--)
num[i]=num[i-];
len++;
num[]=n;
}
void cheng(BigN n)//高精度乘法,这里就不过多解释了,有疑问可以前往 P1303 了解更多
{
BigN c("");
int s=,g=;
for(int i=;i<=len;i++)
for(int j=;j<=n.len;j++)
{
int w=i+j;
s=num[i]*n.num[j];
c.num[w]+=s%;
c.num[w+]+=s/+c.num[w]/;
c.num[w]%=;
}
c.len=len+n.len;
while(c.num[c.len]==&&c.len>=)c.len--;
fz(c);
}
void fz(BigN n) //将一个大整数赋值给例外一个大整数,相当于'='
{
len=n.len;
for(int i=;i<=n.len;i++)
num[i]=n.num[i];
}
bool bj(BigN n) //判断两个大整数的大小,用于找出最大结果
{
if(len>n.len)
return ;
else if(len<n.len)
return ;
else
{
for(int i=len;i>=;i--)
if(num[i]<n.num[i])
return ;
else if(num[i]>n.num[i])
return ;
return -;
}
}
void out() //输出
{
for(int i=len;i>=;i--)
printf("%d",num[i]);
}
}; int n,k,sum[],b[],i,j; //常规定义,不多做解释
BigN mmax(""); int main()
{
char s[]; //s用于读入一个大整数
scanf("%d%d%s",&n,&k,&s);
for(i=;i<strlen(s);i++) //在sum中备份一份原数
sum[i]=s[i]-'';
for(i=n-;i>=(n-k)-;i--) //将b数组中的后k个数赋1,因为使用next_permutation需要让数组升序,否则可能无法找出所有排列方式
b[i]=;
do{
BigN temp(""),all("");//temp用于存放分割后的每一节,all用于计算每种排列方式的结果
i=;
while(i<n)//分割
{
if(i!=)
if(b[i-]==)//如果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)==)//如果这种排列顺序的结果大于之前最大的结果,刷新最大结果
mmax.fz(all);
}while(next_permutation(b,b+n-));//调用next_permutation
mmax.out();//输出
return ;
}

最新文章

  1. Java的对象初始化过程
  2. NSDate 格式化 NSDate to NSString
  3. The Skins of the Substance
  4. [LintCode] Evaluate Reverse Polish Notation 计算逆波兰表达式
  5. DevExpress Crack
  6. Spring MVC 注解和XML的区别
  7. redis.conf 配置详解
  8. slice,substr,substring
  9. cocos2d-x 3.0游戏实例学习笔记 《跑酷》第四步--地图循环&amp;amp;主角加入动作
  10. 转---高并发Web服务的演变——节约系统内存和CPU
  11. 常用bash命令
  12. 通过crontab调度java -jar任务提示&quot;nohup: failed to run command `java&#39;: No such file or directory&quot;
  13. nginx Provisional headers are shown
  14. 使用vue时,报错“exports is not defined”
  15. win10个人助理conrtana软件能否支持用户反馈、后续优化
  16. 34.QT-制作串口助手(并动态检测在线串口,附带源码)
  17. yolo算法解析
  18. vue-router 如何默认显示三级子路由
  19. 数据库和Django model 生成和反向生成
  20. leetcode-algorithms-36 Valid Sudoku

热门文章

  1. vue-cli的安装及版本查看更新
  2. 破解压缩包的几种方式(zip伪加密 爆破 CRC32碰撞 已知明文攻击)
  3. 人生物语&mdash;&mdash;哲海拾贝
  4. windows,linux里的hosts文件
  5. MySQL数据物理备份之tar打包备份
  6. NetScaler的常用配置
  7. unity texture贴图纹理
  8. linux 利用 crontab 实现 程序开机启动/crontab任务的多种实现方法
  9. 第二章python中的一切皆对象
  10. Django+uWSGI+Nginx 部署网站