Dynamical programming

Task
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <sys/types.h>
#include <iostream>
#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.