BZOJ 3193 JLOI2013 地形生成：排序+DP計數合法序列

問題描述

N≤1000 座山，每座有唯一標號 1..N、高度 h、關鍵數 k。排列需滿足：每座山前方比它高的山數量 少於 其關鍵數 k。求：
1. 不同標號序列數
2. 不同等高線（高度）序列數
答案模 2011。

核心觀察

對某山影響的只可能是比它高的山。按高度 降序 處理，高處理時所有更高山已定位。同高度山相互不影響，可一起處理。

問題一：標號序列計數

降序處理到第 i 組（同高度），已放置 i-1 組山。當前組大小 sz，按關鍵數 k 升序排列。第 j 座山（0-based）可插入位置數：

min(i, k_j + 1) + j
// i = 已放置組數 = 當前可用「間隙」上限
// k_j+1 = 關鍵數限制的位置上限（少於k個更高山 → 至多插在第k+1個間隙）
// j = 同組內前面已放j座山，佔用了j個位置

答案乘積模 2011。

問題二：等高線序列計數（DP去重）

同高度山不可區分，需避免重複計數。DP 狀態：
f[t] = 處理完前 i-1 組、當前組已放 t 座山的方案數。
轉移：第 j 座山可插入位置數同上，但需保證插入後相對順序不變（即只能插在當前組已放山的後面或間隙中）。

for each group (height h, size sz, sorted by k):
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for j = 0 .. sz-1:
        limit = min(i, k_j + 1) + j;
        for t = limit down to 0:
            f[t] = (f[t] + (t>0 ? f[t-1] : 0)) % MOD;
// 組內DP結束後，將f合併到全局答案
ans2 = (ans2 * f[sz]) % MOD;

實際代碼中 f 為一維滾動，每組清零重新計算。

樣例驗證

N=2，山1：h=1,k=2；山2：h=2,k=2。
降序：先放山2（高），再放山1。山2：min(1,3)+0=1 位置。山1：min(2,3)+0=2 位置。
標號序列：1×2=2。等高線序列：高度不同，同標號序列 2。輸出 2 2。

關鍵代碼片段

struct Mountain { int h, k; } a[1005];
bool cmp(Mountain x, Mountain y) { return x.h==y.h ? x.ky.h; }

sort(a+1, a+n+1, cmp);
int ans1=1, ans2=1, f[1005];
for (int i=1; i<=n; i=j) {
    memset(f, 0, sizeof(f)); f[0]=1;
    for (j=i; j<=n && a[j].h==a[i].h; j++) {
        int pos = min(i, a[j].k+1) + (j-i);
        ans1 = ans1 * pos % MOD;
        for (int t=j-i+1; t>=1; t--)
            f[t] = (f[t] + f[t-1]) % MOD;
    }
    ans2 = ans2 * f[j-i] % MOD;
}
printf("%d %d\n", ans1%MOD, ans2%MOD);