input:minmax.in output:minmax.out

时间限制: 1000 ms 空间限制: 60000 KB

题目描述

做过了乘积最大这道题,相信这道题也难不倒你。 已知一个数串,可以在适当的位置加入乘号(设加了k个,当然也可不加,即分成k+1个部分),设这k+1个部分的乘积(如果k=0,则乘积即为原数串的值)对m 的余数(即mod m)为x; 现求x能达到的最小值及该情况下k的最小值,以及x能达到的最大值及该情况下的k的最小值(可以存在x的最小值与最大值相同的情况)。

以下是{原题:符文之语}另一种题目描述,题意相同:
{ 当小 FF 来到神庙时,神庙已经破败不堪了。 但神庙的中央有一个光亮如新的石台。小 FF 走近石台,发现石台上有一个数串,而数串的上方刻着一串古老的符文之语。精通古符文之语的小 FF 不费吹灰之力就读懂了文章的意思, 其大意是:
对于石台上的一串数字,你可以在适当的位置加入乘号(设加了 k 个,当然也可不加, 即分成 k+1 个部分),设这 k+1 个部分的乘积(如果 k=0,则乘积即为原数串的值)对 m 的余数(即 mod m)为 x;
现求 x 能达到的最小值及该情况下 k 的最小值,以及 x 能达到的最大值及该情况下的 k 的最小值(可以存在 x 的最小值与最大值相同的情况)。
小 FF 还知道, 如果他找到了正确的答案,那么就可以通往神庙的下层了。但这个问题似乎不太好解决, 小FF 就找到了你,并答应找到财宝以后和你二八分(当然你拿二……)。}

输入

第一行为数串,长度为n 满足2<=n<=1000,且数串中不存在0; 第二行为m,满足2<=m<=50。

输出

四个数,分别为x的最小值 和 该情况下的k,以及x的最大值和 该情况下的k,中间用空格隔开。

样例输入

1
2
4421
22

样例输出

1
0 1 21 0

代码

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
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1001],sum[1001][1001],dp[1001][100];
char c[1001];
int main()
{
freopen("minmax.in","r",stdin);
freopen("minmax.out","w",stdout);
for(int i=0;i<=1000;i++)
for(int j=0;j<=50;j++)
dp[i][j]=0x7f7f7f;
cin>>c>>m;
int len=strlen(c);
for(int i=0;i<len;i++)
a[i+1]=c[i]-'0';
for(int i=1;i<=len;i++)
for(int j=i;j<=len;j++)
sum[i][j]=(sum[i][j-1]*10+a[j])%m;
for(int i=1;i<=len;i++)
dp[i][sum[1][i]]=1;
for(int i=1;i<=len;i++)
{
for(int j=1;j<i;j++)
{
for(int k=0;k<=m-1;k++)
dp[i][(k*sum[j+1][i])%m]=min(dp[i][(k*sum[j+1][i])%m],dp[j][k]+1);
}
}
for(int i=0;i<=m-1;i++)
{
if(dp[len][i]!=0x7f7f7f)
{
cout<<i<<" "<<dp[len][i]-1<<" ";
break;
}
}
for(int i=m-1;i>=0;i--)
{
if(dp[len][i]!=0x7f7f7f)
{
cout<<i<<" "<<dp[len][i]-1<<" ";
break;
}
}
return 0;
}