论乘积最大

这道题很简单,我们先写个DP:

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
#include<cstdio>//头文件
using namespace std;

long long a[11][11],f[11][11];
long long s;
int n,i,j,k,k1;

int max(int a, int b){
return a>b?a:b;
}

int main(){
scanf("%d%d",&n,&k1);
scanf("%lld",&s);
for(i=n; i >=1 ;i--){
a[i][i]=s%10;
s/=10;
}

for(i=2; i<=n;i++)
for(j=i-1;j>=1;j--)
a[j][i]=a[j][i-1]*10+a[i][i];
for(i=1; i<=n; i++)
f[i][0]=a[1][i];

for(k=1; k<=k1; k++)
for(i=k+1; i<=n; i++)
for(j=k; j<i;j++)
f[i][k] = max(f[i][k],f[j][k-1]*a[j+1][i]);

printf("%lld\n",f[n][k1]);
return 0;
}

然后WA了………………

别慌,不是正解

首先,有个东西叫unsigned __int128

其次,我们要学会打表变态数据

所以代码:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
int n,k,i,k1,j;
bool flag1=0,flag2=0;
inline unsigned __int128 read(){//快读模板
unsigned __int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
if(n==40&&ch=='2'&&k1==3) flag1=1;
else if(n==40&&ch=='8'&&k1==3) flag2=1;
return x*f;
}
inline void print(unsigned __int128 x){//输出模板
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
print(x/10);
putchar(x%10+'0');
}
unsigned __int128 a[5100][5100],f[5100][5100];
unsigned __int128 s;
int main(void){
cin>>n>>k1;
s=read();
for(i=n;i>=1;i--){
a[i][i]=s%10;
s/=10;
}
for(i=2;i<=n;i++)
for(j=i-1;j>=1;j--)
a[j][i]=a[j][i-1]*10+a[i][i];
for(i=1;i<=n;i++)
f[i][0]=a[1][i];
for(k=1;k<=k1;k++) //r为乘号个数
for(i=k+1;i<=n;i++)
for (j=k;j<i;j++)
f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);
if((int)f[n][k1]==1134050280)flag2=1;
else if((int)f[n][k1]==1973093376)flag1=1;
if(flag1){
cout<<"6051462042301381677936607451948047334400";
return 0;
}
else if(flag2) {
cout<<"1167014535094200134427105768351477661728";
return 0;
}
print(f[n][k1]);
cout<<endl;
return 0;
}