Задача о стержне

[Александр222]

Строку S, состоящую из десятичных цифр, можно разделить на непустые последовательные подстроки S0, S1, S2,… (если записать их подряд, получим S). Каждая подстрока S[i] задает записанное ею число a[i]. Из чисел, заданных подстроками, образуется многочлен a0 + a1x + a2x^2 + ... Нужно разбить строку S так, чтобы при заданном значении х этот многочлен имел минимальное значение (решений может быть несколько).

Вход. Первая строка текста содержит строку S длиной не больше 100, вторая— значение х (0,01≤x≤99,9).

Выход. В первой строке текста - минимальное значение многочлена, во второй - последовательность подстрок, разделенных пробелом.

Если представить, что мы разделяем не string, а int, то будет ли данное решение верным? Решается методом динамического программирования.

Задача решена методом динамического программирования.
N - длина стержня. k - количество точек разреза

#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;
      }
}

[Александр222]

Александр222,

Добавил обычное решение для строки. Но не понимаю, как сделать это с помощью дп или рекурсии.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

void minPoly(const string &str, double x) {
   vector<double> coefficients;
   if (x <= 1.0) {
      for (int i = 0; i < str.size(); i++) {
         int a = str[i] - '0';
         cout << a << " ";
         coefficients.push_back(a);
      }
   }
   else {
      double L = 0;
      double R = stod(str);
      double tenf = pow(10.0, str.size() - 1.0);
      double xn = 1.0;

      for (int i = 0; i < str.size(); i++) {
         int a = str[i] - '0';
         cout << a;

         L = 10.0*L+a;
         R -= tenf*a*xn;

         if (( tenf - 1.0 )*L > R/xn*(x-1.0)) {
            coefficients.push_back(L);
            L = 0.0;
            R *= x;
            xn *= x;
            cout << " ";
         }
         tenf /= 10.0;
      }
      coefficients.push_back(L);
   }
   cout << '\n';

   double poly = 0.0, xn = 1.0;
   for (double c : coefficients) {
      poly += c*xn;
      xn *= x;
   }
   cout << poly << '\n';
}

int main() {
   string str;
   double x;
   cout << "Enter string: ";   cin >> str;
   cout << "Enter x: ";        cin >> x;
   minPoly(str, x);
}

[Александр222]

Александр222,

Добавил обычное решение для строки. Но не понимаю, как сделать это с помощью дп или рекурсии.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

void minPoly(const string &str, double x) {
   vector<double> coefficients;
   if (x <= 1.0) {
      for (int i = 0; i < str.size(); i++) {
         int a = str[i] - '0';
         cout << a << " ";
         coefficients.push_back(a);
      }
   }
   else {
      double L = 0;
      double R = stod(str);
      double tenf = pow(10.0, str.size() - 1.0);
      double xn = 1.0;

      for (int i = 0; i < str.size(); i++) {
         int a = str[i] - '0';
         cout << a;

         L = 10.0*L+a;
         R -= tenf*a*xn;

         if (( tenf - 1.0 )*L > R/xn*(x-1.0)) {
            coefficients.push_back(L);
            L = 0.0;
            R *= x;
            xn *= x;
            cout << " ";
         }
         tenf /= 10.0;
      }
      coefficients.push_back(L);
   }
   cout << '\n';

   double poly = 0.0, xn = 1.0;
   for (double c : coefficients) {
      poly += c*xn;
      xn *= x;
   }
   cout << poly << '\n';
}

int main() {
   string str;
   double x;
   cout << "Enter string: ";   cin >> str;
   cout << "Enter x: ";        cin >> x;
   minPoly(str, x);
}

Понял, что если S = «12345» то можно сделать так:

s0 = "1", s1 = "2345"
s0 = "1", s1 = "2", s2 = "345"
s0 = "1", s1 = "23", s2 = "45"
...
s0 = "1", s1 = "2", s2 = "3", s3 = "45"
s0 = "12345"

Но как это все реализовать