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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ объединить три 2-мерных массива в один 3-мерный массив http://www.cyberforum.ru/cpp-beginners/thread266763.html
Первый двухмерный задан рандомно. Второй и третий двухмерные заданы как результаты вычислений от функцый (табуляция по Х, У, А и В). Надо что б из этого всего получился 3-мерный массив. Который потом сортируется по возрастанию.
C++ неполадки с кампилятором я сегодня уже писал о том что ищу графическую библиотку для Dev-Cpp на сайте константина полякова нашел то что искал и сделал все следуя инструкциям, но груфака так и не работает. в самой простой прогармме (там же на сайте взял текст) выдает 233 ошибки, причем все относятся к самой библиотеке graphics.h... в чем может быть дело? и как устранить их? http://www.cyberforum.ru/cpp-beginners/thread266750.html
Решение СЛАУ методом Гаусса C++
помогите разобраться!!ВЫдает 85 ошибок!!!! #include <stdio.h> #include <conio.h> #include <tchar.h> #include <iostream> #include <stdlib.h> #include <time.h> #define eps 0.0000000001 class CMatrix
Динамический массив из целых чисел C++
Плохо разбираюсь с массивами, поэтому нужна помощь написать кусок кода, где создается динамический массив и формирующий в нем множества всех целых чисел вида 2^k и 3^k меньших заданного числа N в порядке возрастания. вообще даже соображений нет, вот что накалякал :( #include "stdafx.h" #include <stdio.h> #include <conio.h> #include <iostream.h> int main () { int N, k, a, b; k=1;
C++ родовой класс http://www.cyberforum.ru/cpp-beginners/thread266732.html
написать программу с родовым классом у которого есть поле двумерный массив. Описать метод с помощью которого меняются местами 2 столббца
C++ find_symbols Хочу модифицировать прогу,которая подсчитывает количество символов в заданной строке,а именно: программа должна подсчитать количество больших и маленьких букв.Кто подскажет,что здесь можно изменить? #include<iostream> #include<string.h> #include<stdio.h> using namespace std; void main() { подробнее

Показать сообщение отдельно
zaptos91
0 / 0 / 0
Регистрация: 30.03.2011
Сообщений: 4
30.03.2011, 00:51     Динамическое программирование.Удаление строки
Дана строка 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 02:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru