解題區/解題區 - UVa

UVa 13032 - Marbles in Jars

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有 $N$ 個罐子，其中有一個罐子放置彈珠時，每一個彈珠重量會是其他罐子的 1.1 倍，也就是說其中有一個魔法罐子，在魔法罐子中的彈珠都會特別重。現在限制每一個罐子放置彈珠的數量，請問有多少放置彈珠方案，可以找到魔法罐子。

Sample Input

1
2
3
4
5
6
7
3
3
1 2 3
3
1 2 2
2
2 2

Sample Output

1
2
3
Case 1: 1
Case 2: 0
Case 3: 2

Solution

從題目描述中理解到，要找到魔法罐子最簡單的策略就是每一個罐子都擁有不同數量的彈珠，由於每一個罐子限制彈珠數量不一致，做起來就稍微複雜。

假設先依照可仿製彈珠數量多寡排序，將放置少量的彈珠優先放置在前面，依序討論放入新的罐子又與之前放置不同個數的彈珠的方法數。

定義 dp[i][j] 為前 $i$ 個罐子，其中有一罐放置最多的彈珠 $j$ 個。由於已經由小到大排序好，放入新的罐子，分成兩種情況考慮，其中一種是比 $i$ 個罐子放置更多的彈珠，不然就是放置較少的彈珠數量，數學組合一下即可。時間複雜度 $\mathcal{O}(N M^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, M[128];
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &M[i]);
        sort(M+1, M+1+N);
        
        long long dp[128][128] = {};
        dp[0][0] = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= M[i]; j++) {
                if (j - (i-1) >= 0) {
                    dp[i][j] = dp[i][j] + dp[i-1][j] * (j - (i-1));
                    dp[i][j] %= MOD;
                }
                for (int k = j+1; k <= M[i]; k++) {
                    dp[i][k] = dp[i][k] + dp[i-1][j];
                    dp[i][k] %= MOD;
                }
            }
        }
        
        long long ret = 0;
        for (int i = 0; i <= M[N]; i++)
            ret = (ret + dp[N][i])%MOD;
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}