我一直在努力解决在街头采访了以下问题。 计数记分卡（30分）
在比赛，N玩家互相玩一次。 每场比赛的结果无论是在球员胜率。 有没有关系。 你给包含每个球员的得分在比赛的最后一个记分卡。 一个球员的得分是游戏玩家在比赛中获得了总数。 然而，一些球员的得分可能已经从记分卡删除。 有多少可能的记分卡与输入记分卡是否一致？
输入：第一行包含案件T.牛逼的情况下遵循的数量。 每一种情况下包含在第一行，随后加入N-号码在第二行的数量N。 第i个数字表示S_I，第i个玩家的分数。 如果第i个玩家的分数已被删除，它是由-1表示。
输出：产量T线，包含了每种情况的答案。 输出每个结果模1000000007。
Constraints:
1 <= T <= 20
1 <= N <= 40
-1 <= s_i < N
Sample Input:
5
3
-1 -1 2
3
-1 -1 -1
4
0 1 2 3
2
1 1
4
-1 -1 -1 2
Sample Output:
2
7
1
0
12
说明：对于第一种情况，有2个记分卡可能：0,1,2或1,0,2。 对于第二种情况下，有效的记分卡是1,1,1，0,1,2，0,2,1，1,0,2，1,2,0，2,0,1，2,1,0 。 对于第三种情况，唯一有效的记分卡是{0,1,2,3}。 对于第四种情况，没有有效的记分卡。 这是不可能为双方球员有得分1。
我试图想出通用功能的做法，但我真的想明确使用动态规划这一问题。 你怎么会想到这个问题复发的关系？
Answer 1:
这里是DP解决上述问题
public static int[][] table; // stores the result of the overlapping sub problems
private static int N;
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int testCases = scanner.nextInt();
for (int i = 0; i < testCases; i++) {
N = scanner.nextInt();
int[] scores = new int[N];
for (int j = 0; j < N; j++) {
scores[j] = scanner.nextInt();
}
long result = process(scores) % 1000000007L;
System.out.println(result );
}
}
private static long process(int[] scores) {
int sum = 0;
int amongPlayers = 0; //count no of players whose score has been erased(-1)
for (int i = 0; i < N; i++) {
if (scores[i] != -1) {
sum += scores[i];
} else {
amongPlayers++;
}
}
int noGames = (N * (N -1)) /2; // total number of games
if (sum < noGames) {
int distribute = noGames - sum; // score needed to be distributed;
table = new int[distribute + 1 ][amongPlayers + 1];
for (int m = 0; m <= distribute; m++) {
for (int n = 0; n <= amongPlayers; n++) {
table[m][n] = -1;
}
}
return distribute(distribute, amongPlayers); // distrubute scores among players whose score is erased(-1)
}
else if(sum == noGames){
return 1;
}
return 0;
}
/**
* Dynamic programming recursive calls
* @param distribute
* @param amongPlayers
* @return
*/
private static int distribute(int distribute, int amongPlayers) {
if(distribute == 0 && amongPlayers == 0)
return 1;
if (amongPlayers <= 0)
return 0;
if(distribute == 0)
return 1;
int result = 0;
if (table[distribute][amongPlayers - 1] == -1) {
int zeroResult = distribute(distribute, amongPlayers - 1);
table[distribute][amongPlayers - 1] = zeroResult;
}
result += table[distribute][amongPlayers - 1];
for (int i = 1; i < N ; i++) { // A person could win maximum of N-1 games
if (distribute - i >= 0) {
if (table[distribute - i][amongPlayers - 1] == -1) {
int localResult = distribute(distribute - i,
amongPlayers - 1);
table[distribute - i][amongPlayers - 1] = localResult;
}
result += table[distribute - i][amongPlayers - 1];
}
}
return result;
}
Answer 2:
观察：
序列s [1]，S [2]，...，S [N]是一致的计分卡，这些属性必须持有：
- S [I1] + S [12] + .. + S [IK]> = K *（K - 1）/ 2，其中I1 <I2 <.. <IK（即，对于长度为k的每一个序列）
- S [1] + S [2] + .. + S [N] = N *（N - 1）/ 2
首先，我们需要检查没有被擦除的分数，只用1个条件。 然后把使用动态编程擦除分数。
让我们表示擦除分数B [I]中，不擦除分数[I];
总和{I = 1 ..升} A [1] + {总和I = 1 ..ķ} B [I]> =（K + L）*（K + L - 1）/ 2
总和{I = 1 ..升} A [1] + {总和I = 1 ..ķ} B [I]> = 0 + 1 + ... +（K + L - 1）
总和{I = 1 .. L}（A [1] - （K + I - 1））+ {总和I = 1 ..ķ} B [I]> = 0 + 1 + ... +（K - 1 ）
因此，我们可以预先计算用于每k，总和的最小值{I = 1 .. L}（A [1] - （K + I - 1））/
动态规划：
状态：
DP [k]的[评分] [和]：我们知道前k个最小擦除分数，其值不超过$比分$，与和是他们的总和。
过渡：
跳过得分，DP [k]的[得分] [总和] + = DP [k]的[得分+ 1] [总和];
把$ I $值$得分$ DP [k]的[得分]的分数[总和] + = C [M - k]的[I] * DP [K + 1] [得分+ 1] [总和+ I *得分] ，其中擦除分数米数，C [n]的[K] =组合。
我的代码
Answer 3:
胜的总和应为（NC 2）
减去它们在输入中给出的已知值。 让剩余的总和（NC 2） - X被称为S.让-1的输入的数量是Q.
现在的问题归结为寻找Q变量范围从0到N-1的整数解（最大评分可能的）和总和的其数量为S
让DP [Q] [S]表示q变量，其和S的整体解决方案的数量
然后我们有，
DP[q][s] = Sum (i=0 to N-1) DP[q-1][s-i]
DP [Q] [S]给出溶液
编辑：
观察：当x剩下的人，总胜的数量至少应为X *（X-1）/ 2（当他们打对方）。 因此，在任何时候当q人，s不能超过（NQ）（NQ-1）/ 2 = M
应该有一个更约束DP [Q] [秒]应等于0时s是大于M
Answer 4:
我试图解决这个任务，太，并认为它应该是这样的：
玩家（= N）的数目，未知卡的数量（计数的“-1”）和已知的卡的总和（计数所有卡除“-1”）中给出。 游戏可能总数应为1 + 2 + 3 + ... +（球员-1）：第一个玩家（玩家-1）的对手，第二个玩家（玩家-2）等。
现在，您可以递归地计算可能的记分卡的总和：
初始化（球员，未知卡，知牌之和）为重点和可能的记分卡作为值之和的空HashMap。
如果所有的卡都定义，那么答案是0（如果所有卡的总和等于游戏可能的总数）或1（如果所有卡的总和不等于游戏可能的总数）。
如果不是所有的卡都定义，然后运行一个for循环和一个未知卡设置为0，1，2 ...（玩家-1），并尝试读取从HashMap中的结果。 如果不是在HashMap的调用方法本身并将结果保存在地图上。
递归代码应该是这样的：
def recursion(players: Int, games: Int, unknownCards: Int, knownScore: Int): Int = {
unknownCards match {
case 0 if knownScore != games => 0
case 0 if knownScore == games => 1
case _ =>
map.get(players, unknownCards, knownScore) getOrElse {
var sum = 0
for (i <- 0 until players) sum += main(players, games, unknownCards - 1, knownScore + i)
sum %= 1000000007
map.put((players, unknownCards, knownScore), sum)
sum
}
}
}
Answer 5:
试试这个
import java.util.Scanner;
public class Solution {
final private static int size = 780;
private static long[][] possibleSplits = new long[size][size];
static {
for(int i=0; i < size; ++i)
possibleSplits[i][0] = 1;
for(int j=0; j< size; ++j)
possibleSplits[0][j] = j+1;
for(int i=1; i< size; ++i)
for(int j=1; j < size; ++j)
{
possibleSplits[i][j] = (possibleSplits[i-1][j] + possibleSplits[i][j-1]) % 1000000007;
}
}
public long possibleWays = 0;
public Solution(int n, String scores)
{
long totalScores = 0;
int numOfErasedScores = 0;
for(String str : scores.split(" "))
{
int s = Integer.parseInt(str);
if (s < 0)
++numOfErasedScores;
else
totalScores += s;
}
long totalErasedScores = ncr(n,2) - totalScores;
if(totalErasedScores == 0)
++possibleWays;
else if (totalErasedScores > 0)
partition(n-1, totalErasedScores, numOfErasedScores);
}
private void partition(int possibleMax, long total, int split)
{
if (split == 0)
return;
possibleWays = possibleSplits[(int)total-1][split-1];
if (total > possibleMax)
possibleWays -= split;
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int numberOfTestCases = Integer.parseInt(in.nextLine().trim());
for(int i=0; i< numberOfTestCases; ++i)
{
String str = in.nextLine().trim();
int numberOfPlayers = Integer.parseInt(str);
String playerScores = in.nextLine().trim();
long result = new Solution(numberOfPlayers, playerScores).possibleWays;
System.out.println(result % 1000000007);
}
in.close();
}
public static long ncr(int n, int r)
{
long result = 1;
for(int i= Math.max(n-r, r)+1;i<=n;++i)
result*= i;
result/= fact(Math.min(n-r,r));
return result;
}
public static long fact(int n)
{
long result = 1;
for(int i =2; i<= n; ++i)
result *= i;
return result;
}
}
文章来源: How many possible scorecards are consistent with the input scorecard?
