Национална Олимпиада по Информатика 2004, Задача 2.3. БРОЙ
Уловието на задачата може да прочетете тук.
Решение
Дадена е редицата от числа A1,
A2,..., A2n. Ai Î [0;p]. Нека Si..j
е сумата на числата от Ai до Aj. От всички редици A1, A2,..., A2n, ние се интересуваме от тези, за които е изпълнено S1..n
– Sn+1..2n = k. И по-точно се интересуваме от
техния брой.
Първо ще решим една друга задача и ще покажем
как може да я използваме за решаването на горе-описаната задача. Задачата,
която ще решим е следната. Колко са различните редици от N числа A1, A2,...An,
Ai Î [0;p],
които имат сума на членовете на редицата X. Ще дефинираме функцията F(n,x), която ни
дава търсения отговор за n
числа и сума x. F(0,0) = 1
и F(0,x) = 0 за x ≠ 0.
За n > 0, F(n,x) може да изчислим като присвоим на последното
число в редицата всяка възможна стойност. А именно F(n,x) е равна на сумата от F(n-1,x-i), за всяко i
от интервала [0;p]. Очевидно F(n,x) = 0, за x > n.p, понеже сума на n
числа, всяко не по-голямо от p не
може да е по-голяма от n.p. Също F(n,x) = 0, за x < 0,
понеже всички числа от редицата са неотрицателни. След като дефинирахме рекурентната зависимост за функцията F(n,x),
може чрез метода на динамичното оптимиране да изчислим
последователно стойностите на функцията за всяко n и
x Î [0;n.p].
Как може да използваме вече изчислената
функция F в оригиналната задача. Ако сумата на
първата половина от числа е равна на 0, то сумата на втората половина
трябва да е –k. И броят на различните
решения за сума 0 на първата половина и сума –k на втората е F(n,0).F(n,-k). Аналогично ако
първата половина има сума 1, втората трябва да има сума 1-k и броят на различните решения е F(n,1).F(n,1-k). Аналогично за всички възможни сума на първата половина от 0 до n.p. Сумирайки броят на различните решения за всяка възможна сума на
първата половина ни дава броят на всички решения и така решаваме задачата.
Не трябва да забравяме при реализацията на
задачата да използваме и подходящите типове данни. За тази задача е достатъчно
използването на 64 битови целочислени числа.
Примерна реализация
#include <iostream>
using namespace std;
typedef long long i64;
const int maxn = 10;
const int maxs = 100;
int n, p, k;
i64 ans;
i64 f[maxn][maxs];
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int i, j, r;
void readf();
void writef();
readf();
f[0][0] = 1;
for (i = 1; i <= n; i++)
for (j = 0; j <= n * p; j++)
for (r = 0; r <= min(p, j); r++)
f[i][j] += f[i-1][j-r];
for (i = k; i <= n * p; i++)
ans += f[n][i] * f[n][i-k];
writef();
}
void readf()
{
cin >> n >> p >> k;
}
void writef()
{
cout << ans << '\n';
}
Автор: Иван Анев
обратно към брой 26
|