Условие: http://acm.timus.ru/problem.aspx?space=1&num=1353
мой код с дп даёт WA #11
как нужно тогда правильно её решать?
Или дайте какую-нибудь подсказку :)
Спасибо Petruchcho за помощь)
Задаем матрицу d[i][j], где i это само число, а j-кол-во цифр. Ответом будет d[n][9]. Если мы хотим получить d[i][j], мы суммируем всевозможные варианты первой цифры k числа i для j цифр. Тогда очевидно, что количество вариантов для d[i][j] будет сумма вариантов d[i-k][j-1], так как мы рассматриваем число вариантов для числа, меньшего на k и в котором на одну цифру меньше.
Лень с вашим кодом ковыряться =) Вот мой, если что.
Пусть f[i][j] - число способов представить сумму i, из j слагаемых, каждое из которых меньше либо равно девяти.
Влад, ты как всегда крут, но просили натолкнуть в идеи, а не кидать решение!
Это блог, а не чат)
Хитро. А я такое:
http://pastebin.com/V0Gtz6kC
Забавный факт - сдалось это только после замены
if(prec[j] == a)
ans++;
на
ans += (prec[j] == a);
Это ускорило программу как минимум на 250 мс. Не думал, что это может быть настолько важно.