锐客网

  1. 首页 > it技术 > >

洛谷P1018|洛谷P1018 乘积最大两种做法

目前整理了两种做法
方法一：
设a为输入的字符串，num【i】【j】表示字符串中从下标为i到j（故从0开始）的一串数字。那么可以得到
for(int i=0; i for(int i=0; i for(int j=i+1; j num[i][j]=num[i][j-1]*10+a[j]-'0';
这是一个递推，第一行是设置边界，递推关系式即num[i][j]=num[i][j-1]*10+a[j]-'0';
设f【i】【j】表示在0到i间加入i个乘号的最大乘积，则状态转移方程为：
for(int k=1; k<=x; k++)
for(int i=k; i for(int j=k-1; j f[k][i]=max(f[k][i],f[k-1][j]*num[j+1][i]);
边界设置如下：
for(int i=0; i f[0][i]=num[0][i]; 代码如下，但这样只有60分，AC需要使用高精度乘法，下次再加上

#include #include #include #include using namespace std; const int N=41; char a[N]; int x,n,len; long long f[N][N],num[N][N]; int main() { //freopen("in.txt","r",stdin); cin>>n>>x; cin>>a; for(int i=0; i方法二：

#include #include using namespace std; int n,k,maxx; int a[41]; char ch; void dfs(int x,int ans,int last) { if(x==k) { int mul=0; for(int j=last+1; j>n>>k; for(int i=1; i<=n; i++) { cin>>ch; a[i]=ch-'0'; } dfs(0,1,0); //初始值处理 cout<


这种做法来自sumyt，原文：
题解 P1018 【乘积最大】 - sunyt 的博客 - 洛谷博客
https://www.luogu.org/blog/user17407/solution-p1018
void dfs（三个已插入的乘号个数，当前乘积，上一个插入的乘号的位置）中
第三个形参的说明：比如在1231中插了一个变成：1*231，那么该形参表示的是“*”左边的1的位置
for(int j=last+1; jmul+=a[j]; mul*=10;
} mul+=a[i];
mul表示上一乘号到刚插入的这个乘号之间的数字。
好啦解释（ban yun）完毕。


【洛谷P1018|洛谷P1018 乘积最大两种做法】转载于:https://www.cnblogs.com/Neptune0/p/11379202.html

    推荐阅读


    上一篇：蓝桥杯题目练习 提升篇 [蓝桥杯2016决赛]赢球票

    下一篇：网络流|poj3680 Intervals