|
|
|
|
|
|
|
Вернуться
| 1 Вильчевский Константин, 27 декабря 2009 г. 20:55:05 | |
|
Спасибо за помощь!
|
|
|
| 2 Бабушкин Олег, 27 декабря 2009 г. 17:14:06 | |
|
)) ну да) классическая динамика, все верное, спасибо за разбор)
|
|
|
| 3 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 27 декабря 2009 г. 16:52:46 | |
|
ну да, для данной задачи, конечно, то, что я написал не актуально, а целом в задачах на динамику это полезно
|
|
|
| 4 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 27 декабря 2009 г. 16:50:09 | |
я вижу кол-во разбиений на слагаемые за куб=)
если динамику модифицировать и f(x,y) - будет кол-во разбиений на слагаемое числа x, где наибольшее из слагаемых не больше y (а не как раньше, кол-во разбиений на слагаемые числа x, где наибольшее слагаемое это y), то состояний останется N * (кол-во различных слагаемых), и пересчитываться динамика будет за O(1), общее время O(N * (кол-во различных слагаемых)), вместо ранее O(N * (кол-во различных слагаемых) ^ 2)(в худшем случае, когда в задаче допустимы все слагаемые, это кубическое время) . рекурентная формула: f(n, k) = f(n, k - 1) + f(n - k, k). база динамики: f(0, k) = 1, f(n, 0) = 0(для всех n > 0), ну еще один случай если n < k, f(n, k) = f(n, k - 1)
int n = nextInt();
long[][] dp = new long[n + 1][11];
Arrays.fill(dp[0], 1);
for (int i = 1; i <= n; i++) {
dp[i][0] = 0;
for (int j = 1; j <= 10; j++) {
int e = 1 << (j - 1);
if (e > i) {
dp[i][j] = dp[i][j - 1];
} else {
dp[i][j] = dp[i][j - 1] + dp[i - e][j];
}
}
}
out.println(dp[n][10]);
|
|
|
| 5 Асямов Игорь Сергеевич, 27 декабря 2009 г. 16:48:36 | |
|
a(n)=a(n-1),если n-нечетное и a(n)=a(n-1)+a(n/2),если четное!
|
|
|
| 6 Бабушкин Олег, 27 декабря 2009 г. 16:24:43 | |
Что бы решить задачу В, нужно знать : что такое граф, способы его представления и обхода. Почитай что нибудь по этой теме и без проблем решишь)
Задача G уже была на одной из прошлых олимпиад (почти один в один).
Способов решения много, лично я вписал динамику в рекурсию.
Мысль такая. Число разбиений числа x на сумму это число разбиений числа 1 + числа 2 + числа 4 + ... и так до x.
Что бы не считать разбиение 1 2 и 2 1 два раза, договоримся на каждом следующем шаге брать числа не больше всех предыдущих. (для того и z)
int f(int x, int z)
{
if (a[x][z])
return a[x][z];
int k = 1, res = 0;
if (x == 1 || x == 0)
return 1;
while (k <= x && k <= z)
{
res += f(x - k, k);
k *= 2;
}
a[x][z] = res;
return res;
}
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
