Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<string>
- #include<algorithm>
- #include<cstdio>
- #include<iostream>
- using namespace std;
- struct str_numb {
- int v;
- string st;
- };
- int n, k;
- str_numb numbs[50];
- short w[1000005];
- short ret[1000005];
- short lng[1000005];
- short best[1000005];
- short cur[1000005];
- short q[1000005];
- bool numb_less(str_numb a, str_numb b) {
- return a.st < b.st;
- }
- short rec(int p) {
- if (w[p]) return lng[p];
- for (int i = k - 1; i >=0 ; i--) {
- if (p - numbs[i].v >= 0) {
- cur[p] = rec(p - numbs[i].v);
- if ((cur[p] + 1 + (int)numbs[i].st.length() <= best[p]) || (best[p] == 0)) {
- best[p] = cur[p] + 1 + (int)numbs[i].st.length();
- q[p] = i;
- }
- }
- }
- w[p] = 1;
- lng[p] = best[p];
- ret[p] = q[p];
- return best[p];
- }
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- cin >> n;
- k = 0;
- for (int i = 1; i <= 9; i++) {
- int p = i;
- numbs[k].v = p;
- numbs[k].st = (char)(i + 48);
- k++;
- for (int j = i + 1; j <= 9; j++) {
- p = p * 10 + j;
- if (p > n) break;
- if (j == i + 1) {
- numbs[k].v = p;
- numbs[k].st += (char)(i + 48);
- numbs[k].st += (char)(j + 48);
- k++;
- } else
- {
- numbs[k].v = p;
- numbs[k].st += (char)(i + 48);
- numbs[k].st += "-";
- numbs[k].st += (char)(j + 48);
- k++;
- }
- }
- }
- sort(numbs, numbs + k, numb_less);
- w[0] = 1;
- int i = rec(n);
- i = n;
- while (i != 0) {
- cout << numbs[ret[i]].st;
- if (i - numbs[ret[i]].v != 0) cout << "+";
- i = i - numbs[ret[i]].v;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement