Динамическое программирование выбора кортежей (размер T) из nos, каждый из которых не больше k и сумма S

Ребята это вопрос

В турнире N игроков играют друг против друга ровно один раз. Каждая игра приводит к победе любого из игроков. Там нет никаких связей. Вы дали карту результатов, содержащую оценки каждого игрока в конце турнира. Счет игрока — это общее количество игр, выигранных игроком в турнире. Однако оценки некоторых игроков могли быть стерты из карты результатов. Сколько возможных оценочных карт соответствуют входной оценочной карте?

Входные данные:
Первая строка содержит количество случаев, за которыми следуют случаи T. Каждый случай содержит число N в первой строке, за которым следуют N чисел во второй строке. I-е число обозначает s_i, счет i-го игрока. Если счет i-го игрока был удален, он обозначается как -1.

Выход:
Выведите T строк, содержащих ответ для каждого случая. Выведите каждый результат по модулю 1000000007.

Я сократил его до приведенной выше формы вопроса, но он терпит неудачу на больших входах.
Это начинает давать мне головные боли. Любая помощь будет оценена. У меня есть следующий код … я что-то пропустил в каких-то угловых случаях.

    #include<stdio.h>
long long  solutionMatrix[781][41];
long long
noOfWays (int gamesUndecided, int inHowMany, int noOfPlayers)
{
if (inHowMany > 0 && gamesUndecided >= 0)
{
int i;
long long result;
for (i = noOfPlayers - 1, result = 0; i >= 0; i--)
{
if((gamesUndecided-i)>=0)
{
if (solutionMatrix[gamesUndecided - i][inHowMany - 1] == -1)
solutionMatrix[gamesUndecided - i][inHowMany - 1] = noOfWays (gamesUndecided - i, inHowMany - 1, noOfPlayers);
result += solutionMatrix[gamesUndecided - i][inHowMany - 1];
result %=1000000007L;
}
}
return result%1000000007L;
}
else
return (inHowMany == 0 && gamesUndecided == 0) ? 1 : 0;
}

long long
possibleCards (int score[], int noOfPlayers)
{
int i;
int maxGames = (noOfPlayers * (noOfPlayers - 1)) / 2;
int sumOfGames = 0, unDecided = 0;
for (i = 0; i < noOfPlayers; i++)
{
if (score[i] != -1)
{
if (score[i] >= 0 && score[i] <= noOfPlayers - 1)
{
sumOfGames += score[i];
}
else
return 0;
}
else
unDecided++;
}
if (sumOfGames > maxGames || (unDecided==0 && sumOfGames < maxGames))
return 0;
if (sumOfGames==maxGames && unDecided==0)
return 1;
else
{
int j;
for (i = 0; i < 781; i++)
for (j = 0; j < 41; j++)
solutionMatrix[i][j] = -1;
return noOfWays (maxGames - sumOfGames, unDecided, noOfPlayers)%1000000007L;
}
}

int
main ()
{
int noOfTestCases;
int score[41];
printf("%u\n",0xffffffff);
scanf ("%d", &noOfTestCases);
for (; noOfTestCases > 0; noOfTestCases--)
{
int noOfPlayers;
scanf ("%d", &noOfPlayers);
int i;
for (i = 0; i < noOfPlayers; i++)
{
scanf ("%d", score + i);
}
printf ("%lld\n", possibleCards (score, noOfPlayers));
}
return 0;
}

1

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector