동적 계획 - 최소 및 최대

동적 계획 - 최소 및 최대
[문제 설명]
곱셈이 가장 큰 이 문제를 풀었으니 이 문제도 너를 난처하게 하지 않을 거라고 믿는다.
이미 알고 있는 하나의 수열은 적당한 위치에 곱셈(k개를 추가하면 당연히 추가하지 않아도 된다. 즉, k+1개 부분으로 나눌 수 있다)을 넣고 이 k+1개 부분의 곱셈(k=0을 설정하면 곱셈은 원수열의 값)을 m의 여수(즉modm)를 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
",i,f[n-1][i]);
  
 54:             break;
  
 55:         }
  
 56:     return 0;
  
 57: }
  
 58: