Advertisement
Guest User

Untitled

a guest
Jun 26th, 2017
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None | 0 0
  1. #include<string>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. struct str_numb {
  9.     int v;
  10.     string st;
  11. };
  12.  
  13. int n, k;
  14. str_numb numbs[50];
  15. short w[1000005];
  16. short ret[1000005];
  17. short lng[1000005];
  18. short best[1000005];
  19. short cur[1000005];
  20. short q[1000005];
  21.  
  22.  
  23. bool numb_less(str_numb a, str_numb b) {
  24.     return a.st < b.st;
  25. }
  26.  
  27. short rec(int p) {
  28.     if (w[p]) return lng[p];
  29.     for (int i = k - 1; i >=0 ; i--) {
  30.         if (p - numbs[i].v >= 0) {
  31.             cur[p] = rec(p - numbs[i].v);
  32.             if ((cur[p] + 1 + (int)numbs[i].st.length() <= best[p]) || (best[p] == 0)) {
  33.                 best[p] = cur[p] + 1 + (int)numbs[i].st.length();
  34.                 q[p] = i;
  35.             }
  36.         }
  37.     }
  38.     w[p] = 1;
  39.     lng[p] = best[p];
  40.     ret[p] = q[p];
  41.     return best[p];
  42. }
  43.  
  44. int main() {
  45.     freopen("input.txt", "r", stdin);
  46.     freopen("output.txt", "w", stdout);
  47.     cin >> n;
  48.     k = 0;
  49.     for (int i = 1; i <= 9; i++) {
  50.         int p = i;
  51.         numbs[k].v = p;
  52.         numbs[k].st = (char)(i + 48);
  53.         k++;
  54.         for (int j = i + 1; j <= 9; j++) {
  55.             p = p * 10 + j;
  56.             if (p > n) break;
  57.             if (j == i + 1) {
  58.                 numbs[k].v = p;
  59.                 numbs[k].st += (char)(i + 48);
  60.                 numbs[k].st += (char)(j + 48);
  61.                 k++;
  62.             } else
  63.             {
  64.                 numbs[k].v = p;
  65.                 numbs[k].st += (char)(i + 48);
  66.                 numbs[k].st += "-";
  67.                 numbs[k].st += (char)(j + 48);
  68.                 k++;
  69.             }
  70.         }
  71.     }
  72.     sort(numbs, numbs + k, numb_less);
  73.     w[0] = 1;
  74.     int i = rec(n);
  75.     i = n;
  76.     while (i != 0) {
  77.         cout << numbs[ret[i]].st;
  78.         if (i - numbs[ret[i]].v != 0) cout << "+";
  79.         i = i - numbs[ret[i]].v;
  80.     }
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement