Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
zaptos91
0 / 0 / 0
Регистрация: 30.03.2011
Сообщений: 4
#1

Динамическое программирование.Удаление строки - C++

30.03.2011, 00:51. Просмотров 708. Ответов 1
Метки нет (Все метки)

Дана строка S, состоящая из n маленьких латинских букв. За один ход Вам разрешается удалить один или несколько подряд идущих одинаковых символов. Необходимо удалить все символы из строки S за минимальное количество ходов.

Помогите довести до ума код,защитил алгоритм у преподавателя,а нормальная реализация не выходит.Заодно хотелось бы узнать,оптимальное ли это решение.Спасибо!
*Модераторы,если я запостил не в нужном разделе форума,перенесите мою тему пожалуйста*

Алгоритм - пусть в строке S содержится N символов. Создаём матрицу NxN,на главной диагонали расставляем единицы-кол-во удалений для подстроки длины 1,на диагонали над главной - 2,или 1 в зависимости от того,состоит ли подстрока длинны 2 из одинаковых или разных символов.
Далее, увеличивая длины подстрок, пользуемся следующими формулами:

А(i,j)-подстрока,внутри неё бегаем по К
Если S(i)!=S(k),то в матрицу =>
A(i,j)=1+A(i+1,j)

Иначе - S(i)==S(k) -в матрицу =>
A(i,j)=MIN(A(i+1,k-1)+A(k,j)

Таким образом,в правом верхнем углу матрицы будет ответ.


C++
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
61
62
63
#include <iostream>
#include <fstream>
using namespace std;
 
int main()
{
char S[300];
 
ifstream in("input.txt");
in>>S;
in.close();
 
 
int n = strlen(S);
int **A = new int*[n];
for(int i = 0; i < n; i++)
A[i] = new int[n];
 
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
    if(i!=j)
    A[i][j]=0;
    else
    A[i][i]=1;//главная диагональ
}
for(int i=0;i<n-1;i++)//заполнение диагонали над главной
{
if(S[i]==S[i+1])
A[i][i+1]=1;
else
A[i][i+1]=2;
 
 
}
 
 
bool flag;
 
 
for(int i=2;i<n;i++){
for(int j=0;j<n-i;j++){
    flag=true;
for(int k=j+1;k<i+j;k++){
     if(S[k]==S[j]){
         if(flag)
          A[j][i+j]=A[j+1][k-1]+A[k][i+j];
          flag=false;
          if(A[j][i+j]>=(A[j+1][k-1]+A[k][i+j]))//применение алгоритма к
                                                                  //последующим подстрокам
          A[j][i+j]=A[j+1][k-1]+A[k][i+j];
       
         }
    if(S[k]!=S[j])
         A[j][i+j]=1+A[j+1][i+j];
}
}
}
 
cout<<A[0][n-1];//Ответ
 
 
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2011, 00:51     Динамическое программирование.Удаление строки
Посмотрите здесь:

Динамическое программирование. Разбиение абзаца на строки - C++
Условие: В абзаце есть блоки разной высоты (напрмер, обычные слова и математические символы). Абзац длинный, поэтому его нужно разбить на...

Динамическое программирование - C++
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 1, а...

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...

Динамическое программирование - C++
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда сделать шаг: к магазину или в противоположном направлении. ...

Кубики, динамическое программирование - C++
Здраствуйте! Есть задача ( на украинском) Незважаючи на те, що Петрик П’яточкін ходить до школи, він все ще продовжує...

Метод динамическое программирование - C++
Помогите пожалуйста с задачей.Дано натуральное число N, не превосходящее 1000. За один ход разрешается поделить его на 2 или на 3 (если...

Динамическое программирование. Рыцарь. - C++
Необходимо написать три версии алгоритма для решения предложенной задачи. • неэффективная, при помоши рекуррентного спуска. • с...

Задача на динамическое программирование. - C++
Что не правильно? #include &lt;fstream&gt; #include &lt;iostream&gt; using namespace std; int main() {

Задача на динамическое программирование - C++
Требуется решить задачу на динамическое программирование. Условия:На планете Олимпия очень популярна такая головоломка. На столе...

Динамическое программирование, поиск маршрута - C++
Возможно ли организовать поиск пути с препятствием, используя динамическое программирование? Т.е. что то типа лабиринта.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zaptos91
0 / 0 / 0
Регистрация: 30.03.2011
Сообщений: 4
01.04.2011, 03:51  [ТС]     Динамическое программирование.Удаление строки #2
Ау,люди! Ну подскажите хоть что-нибудь,третий день код переписываю!
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru