3

我一直在尝试解决面试街的以下问题。计分卡（30 分）

在一场锦标赛中，N 名玩家互相对战一次。每场比赛都会导致任一玩家获胜。没有关系。您已经给出了一张记分卡，其中包含每个玩家在比赛结束时的得分。玩家的得分是玩家在锦标赛中赢得的总局数。然而，一些球员的分数可能已经从记分卡中删除了。有多少可能的记分卡与输入记分卡一致？

输入：第一行包含案例 T 的数量。接下来是 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 分是不可能的。

我试图提出通用函数方法，但我真的试图使用动态编程来解决这个问题。你怎么能想到这个问题的递归关系？

4

5 回答 5

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;
}
于 2013-04-22T06:50:41.343 回答
1

观察：

序列 s[1], s[2], ..., s[n] 是一致的记分卡，这些属性必须满足：

  1. s[i1] + s[i2] + .. + s[ik] >= k * (k — 1) / 2，其中 i1 < i2 < .. < ik（即对于每个长度为 k 的子序列）
  2. s[1] + s[2] + .. + s[n] = n * (n — 1) / 2

首先，我们需要检查未擦除的分数，只需使用 1 个条件。然后使用动态编程放置擦除的分数。

让我们表示擦除分数 b[i]，而不是擦除分数 a[i]；

sum{i = 1 .. l} a[i] + sum{i = 1 .. k} b[i] >= (k + l) * (k + l - 1) / 2

sum{i = 1 .. l} a[i] + sum{i = 1 .. k} b[i] >= 0 + 1 + .. + (k + l - 1)

sum{i = 1 .. l} (a[i] - (k + i - 1)) + sum{i = 1 .. k} b[i] >= 0 + 1 + .. + (k - 1 )

所以我们可以预先计算每个 k 的最小值 sum{i = 1 .. l} (a[i] - (k + i - 1))/

动态规划：

状态：

dp[k][score][sum]：我们知道前k个最小擦除分数，它们的值不超过$score$，sum就是它们的总和。

过渡：

  1. 跳过分数，dp[k][score][sum] += dp[k][score + 1][sum]；

  2. 将 $i$ 的得分值 $score$ dp[k][score][sum] += C[m — k][i] * dp[k + i][score + 1][sum + i*score] ，其中 m 个已擦除分数，C[n][k] = 组合。

我的代码

于 2014-08-01T08:13:58.587 回答
0

尝试这个

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;
    }
}
于 2013-12-09T17:58:21.227 回答
0

获胜的总和应该是（NC 2）

减去输入中给出的已知值。让剩余的总和 (NC 2) - x 称为 S。让输入中的 -1 的数量为 Q。

现在的问题归结为找到Q 变量的积分解决方案的数量，范围从 0 到 N-1（可能的最大分数）并且总和为 S

令 DP[q][s] 表示总和为 s 的 q 个变量的积分解数

然后我们有，

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

当 s 大于 M 时，应该还有一个约束 DP[q][s] 应该等于 0

于 2012-09-22T05:53:43.627 回答
0

我也在尝试解决这个任务，并认为它应该是这样的：

给出了玩家的数量（=N），未知牌的数量（计算“-1”）和已知牌的总和（计算除“-1”之外的所有牌）。可能的游戏总数应该是 1 +2 +3 + ... + (players-1)：第一个玩家有 (players-1) 个对手，第二个玩家有 (players-2) 个等等。

现在您可以递归地计算可能的记分卡的总和：

以（玩家、未知牌、已知牌的总和）为键，以可能的记分牌的总和为值，初始化一个空的 hashmap。

如果定义了所有牌，则答案为 0（如果所有牌的总和等于可能的游戏总数）或 1（如果所有牌的总和不等于可能的游戏总数）。

如果未定义所有卡片，则运行 for 循环并将一张未知卡片设置为 0、1、2 ... (players-1) 并尝试从哈希图中读取结果。如果它不在 hashmap 中，则调用方法本身并将结果保存在 map 中。

递归代码应该是这样的：

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
      }
  }
}
于 2013-01-01T20:46:53.287 回答