有多少可能的记分卡与输入记分卡是否一致？ [英] How many possible scorecards are consistent with the input scorecard?

问题描述

我一直在试图解决在街头采访了以下问题。数记分卡（30分）

I have been trying to solve the following problem in interview street. Count Scorecards(30 points)

在一项赛事，N对对方球员打一次。每场比赛的结果无论是在球员胜率。有没有关系。你给了包含每名球员的得分在比赛的最后的记分卡。一个球员的得分是游戏玩家在比赛中获得了总数。然而，一些球员的得分可能会被删除的记分卡。有多少可能的记分卡与输入记分卡一致？

In a tournament, N players play against each other exactly once. Each game results in either of the player winning. There are no ties. You have given a scorecard containing the scores of each player at the end of the tournament. The score of a player is the total number of games the player won in the tournament. However, the scores of some players might have been erased from the scorecard. How many possible scorecards are consistent with the input scorecard?

输入： 第一行包含病例T.牛逼的情况下遵循的数量。每一种情况下包含在第一行，随后加入N-号码在第二行的数量N。的第i个数字表示S_I，第i个游戏者的得分。如果第i个选手的比分已经被删除，这是重新-1 psented $ P $。

Input: The first line contains the number of cases T. T cases follow. Each case contains the number N on the first line followed by N numbers on the second line. The ith number denotes s_i, the score of the ith player. If the score of the ith player has been erased, it is represented by -1.

输出： 输出T线，包含每个个案的答案。输出每个结果模1000000007。

Output: Output T lines, containing the answer for each case. Output each result modulo 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。

Explanation: For the first case, there are 2 scorecards possible: 0,1,2 or 1,0,2. For the second case, the valid scorecards are 1,1,1, 0,1,2, 0,2,1, 1,0,2, 1,2,0, 2,0,1, 2,1,0. For the third case, the only valid scorecard is {0,1,2,3}. For the fourth case, there is no valid scorecard. It is not possible for both players to have score 1.

我试图想出通用功能的做法，但我真的想明确使用动态规划这一问题。你怎么能想到这个问题复发的关系？

I have tried to come up with generic functions approach, but i am really trying to nail down this problem using Dynamic programming. How can you think of recurrence relations for this problem?.

推荐答案

下面是DP解决了上述问题。

Here is the DP solution to the above problem

    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;
}

这篇关于有多少可能的记分卡与输入记分卡是否一致？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！