Динамическое программирование


Реализация. Читаем входные данные и обнуляем последний столбец матрицы a (a[n, i] = 0, 0  i  n)



жүктеу/скачать 0.53 Mb.
бет5/6
Дата19.07.2016
өлшемі0.53 Mb.
#208895
түріРешение
1   2   3   4   5   6

Реализация. Читаем входные данные и обнуляем последний столбец матрицы a (a[n, i] = 0, 0  in).

#include

#include
double a[26][26];
void main(void)

{

int i,j,n;



double x,m0,s[26];

while(scanf("%lf %d",&m0,&n) == 2)

{

for(i=0;i

for(i=0;i<=n;i++) a[n][i] = 0;
Динамически пересчитываем значения i - го столбца через i + 1 – ый (0  in -1). Данные каждого столбца вычисляем сверху вниз, двигаясь от a[i, 0] до a[i, i].
for(i=n-1;i>=0;i--)

for(j=0;j<=i;j++)

{

x = sqrt((m0-j)*s[i]/(10+s[i]/10+a[i+1][j+1]-a[i+1][j]));



if (x > m0-j) x = m0-j;

a[i][j] = (x/(m0-j))*(s[i]/2/x+10+s[i]/10+a[i+1][j+1]) +

(1-x/(m0-j))*(s[i]/x+a[i+1][j]);

}
Выводим результат с 4 десятичными знаками после запятой.


printf("%.4lf\n",a[0][0]);

}

}


9. Распределение оценок [Вальядолид, 10910]. Количество способов, которыми студент может сдать экзамен, равно количеству разложений числа p – n*t на n неотрицательных слагаемых (см. задачу Вальядолид, 10943).

Реализация. Определим размер MAX массива m и объявим сам массив m.
#include

#include

#define MAX 71
int tests,n,t,p,i,j;

int m[MAX][MAX];


Обнуляем массив m. Проведем инициализацию, положив f(i, 1) = f(0, i) = 1 (0  i < MAX). Заметим, что

f(n, k) = f(n, k – 1) + ( f(n – 1, k – 1) + f(n – 2, k – 1) + … f(1, k – 1) + f(0, k – 1) ) =

f(n, k – 1) + f(n – 1, k)

Таким образом, значение m[i, j] можно пересчитать как сумму m[i, j – 1] и m[i – 1, j]. Находим значения всех ячеек массива m, совершая таким образом предвычисления.


void main(void)

{

memset(m,0,sizeof(m));



for(i=0;i

for(i=2;i

for(j=1;j

m[i][j] = m[i][j-1] + m[i-1][j];


Читаем количество тестов tests. Для каждого теста вводим значения n, t, p. Положим t = t – n * p. Выводим результат, хранящийся в ячейке m[n, t].
scanf("%d",&tests);

while(tests--)

{

scanf("%d %d %d",&n,&t,&p);



t -= n*p;

printf("%d\n",m[n][t]);

}

}
10. Как Вы прибавляете? [Вальядолид, 10943]. Обозначим через f(n, k) количество разбиений числа n на k неотрицательных слагаемых. Если при разбиении числа n на k неотрицательных слагаемых последнее (k - ое) слагаемое равно i (0  in), то далее число n – i следует разбить на k – 1 слагаемых, что можно совершить f(n – i, k – 1) способами. Поскольку 0  in, то общее число разбиений f(n, k) равно f(n, k – 1) + f(n – 1, k – 1) + f(n – 2, k – 1) + … f(1, k – 1) + f(0, k – 1). Или то же самое что



f(n, k) =

Очевидно, что f(n, 1) = 1, так как количество способов разбить число n на одно слагаемое равно единице (этим слагаемым будет само число n). Имеет место соотношение f(0, k) = 1, так как единственным разложением числа 0 на k слагаемых будет 0 = 0 + 0 + … + 0 (k раз). Заведем массив m, в котором положим m[k, n] = f(n, k), 1  k, n  100. Индексы массива m и функции f переставлены для удобства программирования: очередная k - ая строка массива m пересчитывается через предыдущую (k – 1) - ую строку.


Пример. Для n = 20 и k = 2 существует 21 разбиение: 0 + 20, 1 + 19, 2 + 18, ..., 19 + 1, 20 + 0. Для начальных значений n, k таблица m[k, n] имеет вид:


k \ n

0

1

2

3

4

5

1

1

1

1

1

1

1

2

1

2

3

4

5

6

3

1

3

6

10

15

21

4

1

4

10

20

35

56

Реализация. Определим размер MAX массива m и объявим сам массив m.

#include

#include

#define MAX 101


int i,j,n,k;

int m[MAX][MAX];


Обнулим массив m. Проведем инициализацию, положив f(i, 1) = f(0, i) = 1 (0  i < MAX). Заметим, что

f(n, k) = f(n, k – 1) + ( f(n – 1, k – 1) + f(n – 2, k – 1) + … f(1, k – 1) + f(0, k – 1) ) =

f(n, k – 1) + f(n – 1, k)

Таким образом, значение m[i][j] можно пересчитать как сумму m[i][j – 1] и m[i – 1][ j], взятую по модулю 1000000.


void main(void)

{

memset(m,0,sizeof(m));



for(i=0;i

for(i=2;i

for(j=1;j

m[i][j] = (m[i][j-1] + m[i-1][j]) % 1000000;


Для каждой входной пары чисел n и k выводим результат, хранящийся в ячейке m[k, n].
while(scanf("%d %d",&n,&k),n+k>0)

printf("%d\n",m[k][n]);

}
11. Задача группирования [Вальядолид, 11026]. Пусть а1, a2, …, an – заданные n чисел. Обозначим через Fik (ik) сумму всех возможных произведений по k чисел, взятых среди первых i чисел a1, …, ai. Построим следующую таблицу Fik:


i \ k

1

2

3

1

a1







2

a1 + a2

a1a2




3

a1 + a2 + a3

a1a2 + a1a3 + a2a3

a1a2a3

Имеют место следующие рекуррентные соотношения:

Fi1 = F(i-1)1 + ai, Fii = F(i-1) (i-1) * ai, 1  in

Fik = F(i-1)k + F(i-1) (k-1) * ai, 1  in, 1 < k < i



Значения каждой следующей строки пересчитываются через значения предыдущей строки, поэтому в памяти достаточно хранить один линейный массив d размера 1000. При этом пересчет значений i - ой строки следует начинать с конца: сначала вычислить Fii, потом Fi(i-1) и так далее до Fi1. Все вычисления следует проводить по модулю m.

Пример. Рассмотрим первый тест. Построим две таблицы: вычисления во второй будут производиться по модулю m = 10, а в первой – нет.

i \ k

1

2

3

4




i \ k

1

2

3

4

1

1













1

1










2

3

2










2

3

2







3

6

11

6







3

6

1

6




4

10

35

50

24




4

0

5

0

4

Ответом является максимальное число в четвертой строке второй таблицы.

Реализация. Объявим линейный массив d, в котором будут пересчитываться значения Fik.
#include

#include


long long n,m,i,j;

long long num,res,d[1000];


void main(void)

{
Вводим количество чисел n и значение m. Для каждого входного теста изначально обнуляем массив d. Первое число a1 заносим в d[0].


while(scanf("%lld %lld",&n,&m),n+m>0)

{

memset(d,0,sizeof(d));



scanf("%lld",&d[0]);
Вводим значение num = ai+1 (1  i < n) и пересчитываем значения Fik, k = i, i – 1, …, 1 по выше приведенным рекуррентным формулам. Все вычисления проводим по модулю m.
for(i=1;i

{

scanf("%lld",&num);



d[i] = (d[i-1] * num) % m;

for(j=i-1;j>0;j--) d[j] = (d[j-1]*num+d[j]) % m;

d[0] = (d[0] + num) % m;

}
Находим максимальное значение среди элементов массива d и заносим его в переменную res. Выводим результат.


res = d[0];

for(i=1;i res) res = d[i];

printf("%lld\n",res);

}

}


12. Подсчет общих подпоследовательностей [Топкодер, раунд 298, дивизион 1, уровень 3]. В ячейке f[i][j][k] будем хранить количество общих подпоследовательностей строк a1a2…ai, b1b2…bj и c1c2…ck., где ai = bj = ck. Если для тройки (i, j, k) последнее равенство не выполняется, то полагаем f[i][j][k] = 0. Если i = 0, то считаем, что строка a пустая. Аналогично при j = 0 (k = 0) считаем, что строка b (c) пустая. Положим f[0][0][0] = 1, считая, что общей подпоследовательностью трех пустых строк является пустая строка.

Искомое количество общих подпоследовательностей трех строк a, b и c равно



или – 1

где l, m, n – длины соответственно строк a, b и c.

Вычисление значений f[i][j][k] совершаем следующим образом. Перебираем все возможные значения троек (i, j, k) и для каждого значения f[i][j][k], большего нуля (ai = bj = ck) перебираем все буквы латинского алфавита и для каждой буквы ищем ее появление во всех строках в позициях, больших соответственно i, j и k. Пусть такими позициями будут x, y и z. Добавляем к f[x+1][y+1][z+1] значение f[i][j][k] (индексы сдвинуты на 1, так как нумерация массивов в Си начинается с нуля, а индексу 0 в массиве f соответствует пустая строка).
Пусть a = b = c = “abc”. Тогда

f[0][0][0] = 1, общая подпоследовательность (“”, “”, “”).

f[1][1][1] = 1, общая подпоследовательность (“a”, “a”, “a”).

f[2][2][2] = 2, общие подпоследовательности (“b”, “b”, “b”), (“ab”, “ab”, “ab”).

f[3][3][3] = 4, общие подпоследовательности (“c”, “c”, “c”), (“bc”, “bc”, “bc”),

(“ac”, “ac”, “ac”), (“abc”, “abc”, “abc”).

Остальные значения f[i][j][k] равны нулю.

Количество общих подпоследовательностей равно 1 + 2 + 4 = 7.


#include

#include

#define i64 long long

using namespace std;


i64 f[51][51][51],res;
class CountingCommonSubsequences

{

public:



i64 countCommonSubsequences(string a, string b, string c)

{

int i,j,k,x,y,z;



f[0][0][0] = 1; res = 0;

for(i=0;i<=a.size();i++)

for(j=0;j<=b.size();j++)

for(k=0;k<=c.size();k++)

if (f[i][j][k] > 0)

{

for(char ch = 'a'; ch <= 'z';ch++)



{

x = a.find(ch,i); y = b.find(ch,j); z = c.find(ch,k);

if (x != string::npos && y != string::npos && z != string::npos)

f[x+1][y+1][z+1] += f[i][j][k];

}

res += f[i][j][k];



}

return res-1;

}

};
13. Исправить расстановку скобок [Топкодер, раунд 301, дивизион 2, уровень 3]. Обозначим через f(i, j) наименьшее количество символов, которое можно изменить так, чтобы подстрока sisi+1…sj-1sj стала правильной. Тогда имеют место соотношения:



1. f(i, j) = 0 при i > j, так как в таком случае подстрока будет пустой строкой.

2. f(i, j) = f(i + 1, j – 1) + enc(si ,sj). Делаем так, чтобы символ si был открывающейся скобкой, а sj – соответствующий ему закрывающейся скобкой. Далее рекурсивно рассматриваем подстроку si+1…sj-1.

Функция enc(si ,sj) возвращает:

а) 0, если символы si и sj являются соответствующими открывающейся и закрывающейся скобками;

б) 2, если символ si является закрывающейся скобкой, а sj – открывающейся;

в) 1 иначе. В этом случае достаточно изменить один из символов si или sj так, чтобы они образовали правильную скобочную пару;

3. f(i, j) = (f(i, k) + f(k+1, j)). Подстроку sisi+1…sj-1sj рассматриваем как последовательность двух правильных скобочных структур: si…sk и sk+1…sj.

В ячейках m[i][j] массива m сохраняем значения f(i, j). Ответом задачи будет f(0, |s| – 1), где s – входная строка.


#include

#include

#include

#define min(i,j) (i

using namespace std;
int m[51][51];

string s;


int enc(char c, char d)

{

string p="([{)]}";



if (p.find(c)/3>0 && p.find(d)/3<1) return 2;

if (p.find(c)%3==p.find(d)%3 && c!=d) return 0;

return 1;

}
int f(int i, int j)

{

if (i>j) return 0;



if (m[i][j]>=0) return m[i][j];

int r = f(i+1,j-1) + enc(s[i],s[j]);

for(int k=i+1;k

r = min(r,f(i,k) + f(k+1,j));

return m[i][j]=r;

}
class CorrectingParenthesization

{

public:


int getMinErrors(string s)

{

::s = s;



memset(m,-1,sizeof(m));

return f(0,s.size()-1);

}

};
14. Просуммировать всех [Топкодер, раунд 311, дивизион 1, уровень 2]. Пусть функция f(x) вычисляет сумму цифр всех чисел от 0 до x. Тогда ответом задачи будет значение f(upperBound) – f(lowerBound – 1). Заведем массив dp[10][11], в котором dp[i][j] равно сумме цифр всех j - значных чисел, первая цифра которых равна i. Изначально положим dp[i][0] = 0. Ячейка dp[0][j] содержит сумму цифр всех чисел, содержащих менее j цифр, то есть сумму цифр всех (j – 1) - значных чисел, начинающихся с любой цифры включая ноль:



dp[0][j] =

Любое j - значное число, первая цифра которого равна i, образуется из (j – 1) - значного числа приписыванием впереди цифры i. Поэтому сумма их цифр равна сумме цифр (j – 1) - значных чисел плюс цифра i, умноженная на количество j - значных чисел с первой цифрой i (количество последних равно 10j-1). Получаем соотношение:

dp[i][j] = dp[0][j] + 10j-1 * i

Остается описать вычисление функции f(x). Очевидно, что f(0) = 0. Пусть x = . Для вычисления f(x) разобъем множество чисел от 0 до x на два подмножества:

1. Числа от 0 до . Сюда входят все (n + 1) - значные числа, начинающиеся цифрой 0, 1, …, an – 1. Сумма их цифр равна dp[0][n + 1] + dp[1][n + 1] + … + dp[an – 1][n + 1].

2. Числа от 0 до . Цифра an в этих числах встречается ( + 1) раз. Сумма остальных цифр этого множества равна f().

Таким образом

f(x) = + an * ( + 1) + f()

Функция info(x, *len, *FirstDigit, *Rest) по входному значению x возвращает количество знаков в числе len, первую цифру числа FirstDigit и число Rest, полученное зачеркиванием первой цифры в числе x.
#include

#define i64 __int64


i64 dp[10][11];

int digits[10];


void info(int x,int *len,int *FirstDigit,int *Rest)

{

int pow10 = *len = 1;*Rest = 0;



while(x > 9)

{

(*len)++;



*Rest = *Rest+(x%10)*pow10;

x /= 10; pow10 *= 10;

}

*FirstDigit = x;



}
i64 f(int x)

{

int i,len,FirstDigit,Rest;



i64 res;

if (!x) return 0;

info(x,&len,&FirstDigit,&Rest);

for(res=i=0;i

res += dp[i][len];

return res + FirstDigit*(Rest+1) + f(Rest);

}
class SumThemAll

{

public:



i64 getSum(int lowerBound, int upperBound)

{

int i,j,k;



for (i = 0;i<10;i++) dp[i][0] = 0;

for (k=j=1;j<11;j++)

{

dp[0][j] = 0;



for (i = 0; i < 10; i++) dp[0][j] += dp[i][j - 1];

for (i = 0; i < 10; i++) dp[i][j] = dp[0][j] + k * i;

k *= 10;

}

return f(upperBound) - f(lowerBound-1);



}

};

Рекурсивная реализация. Рассмотрим рекурсивную реализацию функции f(x). Суммирование цифр чисел от 0 до x = разобьем на две части:

1. суммирование цифр чисел от 0 до ;

2. суммирование цифр чисел от до ;

Рассмотрим первое множество чисел. На последней позиции повторяется последовательность из чисел 0, 1, …, 9 x / 10 раз. Сумма цифр от 0 до 9 равна 45, поэтому сумма единиц в числах первого множества равна x / 10 * 45. Сумма цифр, стоящих на других местах, равна 10 * f(x / 10 – 1).

Сумма цифр в числах второго множества состоит из суммы цифр единиц (0 + 1 + … + a0) и суммы цифр числа = x /10, умноженного на количество чисел во множестве, то есть на (a0 + 1). Положим temp = a0 = x % 10. Пусть sum(x) – функция, вычисляющая сумму цифр числа x. Тогда сумма цифр всех чисел второго множества равна

(temp + 1) * sum(x / 10) + temp * (temp + 1) / 2
#include

#define i64 __int64


int sum (int x)

{

return (!x) ? 0 : x%10 + sum(x/10);



}
i64 f(i64 x)

{

if (x<=0) return 0;



i64 res = x / 10 * 45;

i64 temp = x % 10;

res = res + 10*f(x/10-1) + (temp+1)*sum(x/10) + temp*(temp+1)/2;

return res;

}
class SumThemAll

{

public:



i64 getSum(int lowerBound, int upperBound)

{

return f(upperBound) - f(lowerBound-1);



}

};


жүктеу/скачать 0.53 Mb.

Достарыңызбен бөлісу:
1   2   3   4   5   6



©dereksiz.org 2024
әкімшілігінің қараңыз
    Басты бет