Petrozavodsk Summer 2017 JOI TST 2012 Selection | Kangaroo | 动态规划

G: Kangaroo

题目大意

有$n(1\leq n\leq 300)$只袋鼠，每个袋鼠大小为$a_i$，袋子大小为$b_i$。袋鼠袋鼠至多装1只袋鼠，且满足被装袋鼠的大小小于袋子的大小。一个装袋鼠的合法方案指的是不存在一只袋鼠可以装进其他袋鼠的袋子里。问有多少种装袋鼠的方法。

题解

令$f_{i,j,k}$表示对于前$i$大的袋鼠，被分成$j$组，有$k$个袋鼠的袋子必须要装袋鼠（即存在袋鼠能装进袋子里，但目前还没有装）。那么答案显然是$\sum_j f_{n,j,0}$，即k=0表示没有袋鼠能装。

那么有3种情况：

• 第$i+1$只袋鼠新开一组放，那么$f_{i,j,k}\rightarrow f_{i+1,j+1,all_{i+1,j}}$
• 第$i+1$只袋鼠放进$k$个袋鼠的袋子里，那么有$k$种选择，$kf_{i,j,k}\rightarrow f_{i+1,j,k-1}$
• 第$i+1$只袋鼠放进$k$个袋鼠以外的袋子里，那么有$all_{i,j}-k$种方案，$(all_{i+1,j}-k)f_{i,j,k}\rightarrow f_{i+1,j,k}$

令$cnt_i$表示有多少只袋鼠可以装$i$。
$all_{i,j}$表示前$i-1$只袋鼠已经有j组有多少只袋鼠还可以装$i$（因为有些袋鼠已经装了其他的袋鼠），那么有$all_i=cnt_i-(i-1-j)$。因为$cnt_i$表示能装$i$的袋鼠有多少只，那么如果已经装了其他袋鼠了的袋鼠，一定能装$i$，因此我们只要$cnt_i$减去已经装了其他袋鼠了的袋鼠就可以得到还有多少只袋鼠能装 i i <script type="math/tex" id="MathJax-Element-1341">i</script>。

那么剩下的就很简单了。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
#define FOR(i,j,k) for(i=j;i<=k;++i)
#define rep(i,j,k) for(i=j;i<k;++i)
typedef long long ll;
const ll MOD = 1e9 + 7;
const int N = 305;
int included[N];
ll dp[2][N][N];
pair<int, int> c[N];
int main()
{
    int i, j, k, n;
    scanf("%d", &n);

    FOR(i,1,n) scanf("%d%d", &c[i].first, &c[i].second);
    sort(c + 1, c + n + 1, greater<pair<int, int>>());
    FOR(i,1,n) FOR(j,1,i)
        if (c[i].first < c[j].second)
            included[i]++;

    ll ans = 0;
    dp[0][0][0] = 1;
    FOR(i,1,n) 
    {
        int p = i & 1;
        memset(dp[p], 0, sizeof dp[p]);
        FOR(j,0,i)
        {
            int t = included[i] - (i - 1 - j);
            FOR(k,0,t)
            {
                (dp[p][j][k] += (dp[p ^ 1][j][k] * (t - k)) % MOD) %= MOD;
                if (k > 0) // 2.
                    (dp[p][j][k - 1] += (dp[p ^ 1][j][k] * k) % MOD) %= MOD;
                (dp[p][j + 1][t] += dp[p ^ 1][j][k]) %= MOD; // 1.
            }
        }
    }

    FOR(j,0,n)
        (ans += dp[n & 1][j][0]) %= MOD;
    printf("%lld\n", ans);

    return 0;
}