### Dynamical programming

The string S, consisting of decimal digits, can be divided into non-empty consecutive substrings S0, S1, S2, ... (if we write them in a row, we get S). Each substring S[i] specifies the number a[i] written by it. From the numbers given by substrings, it forms the polynomial a0 + a1 * x ^ 2 + a2 * x ^ 3 ...
It is necessary to split S so that for a given value this polynomial has a minimum value (there may be several solutions).

Input. The first line of text contains the length no more than 100, the second - the value x (0.01≤x≤99.9).
Output. The first line of text contains the minimum value of the polynomial, the second sequence of space-delimited substrings.

I have some code but it is for int. How can I do it with the help string?(Dynamical programming)

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960`` ``````#include #include #include #define K 202 #define INFTY INT_MAX int k, n; int a[K][K]; int l[K]; void print_brackets(int start, int end); int main(int argc, char* argv[]) { int i, j, m, k, n; std::cin >> n >> k; l[0] = 0; for(i = 1 ; i <= k ; i++) std::cin >> l[i]; l[++k] = n; for(i = 0 ; i <= k; i++) a[i][i] = a[i][i+1] = 0; for(m = 2; m <= k ; m++) for(i = 0 ; i + m <= k ; i++) { int L = l[i+m] - l[i]; a[i][i+m] = INFTY; for(j = 1 ; j < m; j++) if(a[i][i+m] > a[i][i+j] + a[i+j][i+m]) a[i][i+m] = a[i][i+j] + a[i+j][i+m]; a[i][i + m] += L; } print_brackets (0, k); putc('\n', stdout); std::cout << a[0][k]; system("pause"); return 0; } void print_brackets(int start, int end) { int L = l[end] - l[start]; int i, j, m; if(end - start <= 1){ for(i = start ; i < end; i++) std::cout << l[i]; std::cout << l[end]; } else for(j = 1 ; j < end - start ; j++ ) if(a[start][end] == a[start][start+j] + a[start+j][end] + L) { std::cout << "( "; print_brackets(start, start+j ); std::cout << ", "; print_brackets(start+j, end ) ; std::cout << " )"; break; } }``````
Last edited on
Registered users can post here. Sign in or register to post.