【问题描述】
做过了乘积最大这道题，相信这道题也难不倒你。
已知一个数串，可以在适当的位置加入乘号（设加了k个，当然也可不加，即分成k+1个部分），设这k+1个部分的乘积（如果k=0,则乘积即为原数串的值）对m 的余数（即mod m）为x;
现求x能达到的最小值及该情况下k的最小值，以及x能达到的最大值及该情况下的k的最小值（可以存在x的最小值与最大值相同的情况）。
【输入】
第一行为数串，长度为n 满足2<=n<=1000，且数串中不存在0；
第二行为m，满足2<=m<=50。
【输出】
四个数，分别为x的最小值 和 该情况下的k，以及x的最大值和 该情况下的k，中间用空格隔开。
【样例输入】
4421
22
【样例输出】
0 1 21 0
既然题目要求的都是乘号的最小值，那么我们自然地就会想到动归数组中记录乘号的最小值。f[i][j]表示0~i的串达到j这个余数所需最少的乘号数。预处理b[i][j]表示从i到j的数对m的余数。
1: #include <stdio.h>
2: #include <string.h>
3: #define MAXINT 100000
4: #define maxn 1010
5:
6: int f[maxn][50];
7: int b[maxn][maxn];
8: int n,m;
9: char s[maxn];
10: int tem;
11:
12: int main()
13: {
14: freopen("input.txt","r",stdin);
15: freopen("output.txt","w",stdout);
16:
17: scanf("%s%d",s,&m);
18: n=strlen(s);
19: for (int i=0;i<n;++i)
20: for (int j=0;j<m;++j)
21: f[i][j]=MAXINT;
22: for (int i=0;i<n;++i)
23: {
24: tem=(tem*10+s[i]-'0')%m;
25: f[i][tem]=0;
26: }
27: for (int i=0;i<n;++i)
28: {
29: tem=0;
30: for (int j=i;j<n;++j)
31: {
32: tem=(tem*10+s[j]-'0')%m;
33: b[i][j]=tem;
34: }
35: }
36: for (int i=0;i<n;++i)
37: for (int j=0;j<m;++j)
38: if (f[i][j]<MAXINT)
39: for (int k=i+1;k<n;++k)
40: {
41: tem=(j*b[i+1][k])%m;
42: if (f[i][j]+1<f[k][tem]) f[k][tem]=f[i][j]+1;
43: }
44: for (int i=0;i<m;++i)
45: if (f[n-1][i]<MAXINT)
46: {
47: printf("%d %d ",i,f[n-1][i]);
48: break;
49: }
50: for (int i=m-1;i>=0;--i)
51: if (f[n-1][i]<MAXINT)
52: {
53: printf("%d %d\n",i,f[n-1][i]);
54: break;
55: }
56: return 0;
57: }
58: