【Luogu1018】乘积最大

Source and Judge

NOIP2000 提高组 T2
Luogu1018
Caioj1501

Problem

【Brief description】
设有一个长度为N的数字串,
要求使用K个乘号将它分成K+1个部分,
找出一种分法,使得这K+1个部分的乘积能够为最大。
【Input】
第一行共有2个自然数N,K
第二行是一个长度为N的数字串。
【Output】
最大乘积
【Limited conditions】
6≤N≤40,1≤K≤6
【Sample input】
4 2
1231
【Sample output】
62
【Sample explanation】

Record

30min

Analysis

请先思考后再展开

当年的梦魇
f[i][k]=max( f[j][k-1]*(j+1~i) )

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//*******************头文件******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
//*******************全局常量****************
//*******************全局定义****************
char s[50];
int f[50][8];
//*******************实现******************
int jh(int l,int r)
{
int ans=0;
for(int i=l;i<=r;i++) ans=ans*10+s[i]-'0';
return ans;
}
//*******************主函数******************
int main()
{
int n,K;scanf("%d%d%s",&n,&K,s+1);
for(int i=1;i<=n;i++) f[i][0]=jh(1,i);
for(int k=1;k<=K;k++)
{
for(int i=k+1;i<=n;i++)
{
for(int j=k;j<i;j++)
{
f[i][k]=mymax(f[j][k-1]*jh(j+1,i),f[i][k]);
}
}
}
printf("%d",f[n][K]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/87af.html
转载请注明出处,谢谢!