POJ 1239 Increasing Sequences [DP]

제목: 생략.
사고방식: 두 번 dp를 진행한다.
첫 번째 dp는 앞에서 뒤로 dp[x]로 x위에서 앞으로 dp[x]위를 표시하면 하나의 숫자를 구성할 수 있고 앞의 수조와 제목의 요구에 부합된다.마지막으로 구한 dp[n]는 마지막 숫자의 길이입니다.
문제는 모든 풀이에서 앞의 숫자가 가장 큰 것을 출력해야 한다는 요구도 있다.따라서 dp를 한 번 더 진행하여 뒤에서 앞으로 나아가야 한다.
코드를 구체적으로 보아라, 애초에 다른 사람의 코드를 보고서야 비로소 알아차렸다.
 

 1 #include<stdio.h>

 2 #include<string.h>

 3 char num[85];

 4 int dp[85], n;

 5 bool judge(int st1,int len1,int st2,int len2)

 6 {

 7     while (num[st1] == '0' && len1) st1++, len1--;

 8     while (num[st2] == '0' && len2) st2++, len2--;

 9     if (len1 < len2) return 1;

10     else if (len1 > len2) return 0;

11     else

12     {

13         for (int i = 0; i < len1; i++)

14         {

15             if (num[st1+i] < num[st2+i]) return 1;

16             if (num[st1+i] > num[st2+i]) return 0;

17         }

18     }

19     return 0;

20 }

21 void print(int pos)

22 {

23     if (pos > n) return;

24     if (pos != 1) printf(",");

25     for (int i = pos; i < pos + dp[pos]; i++)

26         printf("%c", num[i]);

27     print(pos + dp[pos]);

28 }

29 int main()

30 {

31     while (~scanf("%s", num + 1) && strcmp(num + 1, "0"))

32     {

33         n = strlen(num + 1);

34         dp[1] = 1;

35         for (int i = 2; i <= n; i++)

36         {

37             dp[i] = i;

38             for (int j = i - 1; j >= 1; j--)

39                 if (judge(j - dp[j] + 1, dp[j], j + 1, i - j))

40                 {

41                     dp[i] = i - j;

42                     break;

43                 }

44         }

45         int pos = n - dp[n] + 1;

46         dp[pos] = dp[n];

47         for (int i = pos - 1; i >= 1; i--)

48         {

49             if (num[i] == '0')

50             {

51                 dp[i] = dp[i+1] + 1;

52                 continue;

53             }

54             for (int j = pos; j > i; j--)

55                 if (judge(i, j - i, j, dp[j]))

56                 {

57                     dp[i] = j - i;

58                     break;

59                 }

60         }

61         print(1);

62         printf("
");

63     }

64     return 0;

65 }