【問題描述】
做過了乘積最大這道題，相信這道題也難不倒你。
已知一個數(shù)串，可以在適當(dāng)?shù)奈恢眉尤氤颂枺ㄔO(shè)加了k個，當(dāng)然也可不加，即分成k+1個部分），設(shè)這k+1個部分的乘積（如果k=0,則乘積即為原數(shù)串的值）對m 的余數(shù)（即mod m）為x;
現(xiàn)求x能達到的最小值及該情況下k的最小值，以及x能達到的最大值及該情況下的k的最小值（可以存在x的最小值與最大值相同的情況）。
【輸入】
第一行為數(shù)串，長度為n 滿足2<=n<=1000，且數(shù)串中不存在0；
第二行為m，滿足2<=m<=50。
【輸出】
四個數(shù)，分別為x的最小值 和 該情況下的k，以及x的最大值和 該情況下的k，中間用空格隔開。
【樣例輸入】
4421
22
【樣例輸出】
0 1 21 0
既然題目要求的都是乘號的最小值，那么我們自然地就會想到動歸數(shù)組中記錄乘號的最小值。f[i][j]表示0~i的串達到j(luò)這個余數(shù)所需最少的乘號數(shù)。預(yù)處理b[i][j]表示從i到j(luò)的數(shù)對m的余數(shù)。
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: