题解 P2467 【[SDOI2010]地精部落】

学委 · 2018-09-04 20:04:45 · 题解

我觉得先做卡牌游戏（蓝题），这道题不一定比那题难，只要有逆向DP的思维就好了。

题意就是给1到n进行排列，排列后对于任意一个数，两边的数都比它大，或都比它小。求方案数。

如果从头开始递推，取走一个高度以后，发现“取走的是第几高的高度”对后面的递推是有影响的，非常棘手。但是

如果从“还剩1个高度没有取”的方案数，

反推出“还剩2个高度没有取”的方案数，

反推出“还剩3个高度没有取”的方案数……

递推就变得顺利，我发现逆向递推还是经常派得上用场的。

如果你没打过卡牌游戏的话，你可以

(1)做掉那道蓝题，然后你可能再想想就会这道题了。

(2)试试往下看。

怎么想到可以逆向递推？

假设这里有 i 个高度。如果取了第 j 高的作为第一个，下一个我可以

(1)“往高里取”，使下一个成为山峰。当然，这里有许多比 j 更高的高度 H，都是可能的山峰。为了保证 H 是一个山峰，再下一个只能取比 H 低的。

可用 f[i][j][0] 表示有 i 个数时，选取第 j 高的，再往高里取的方案数，用 f[i][j][1] 表示往低里取的方案数。

求 f[i][j][0] 的办法是：

for(int H = j; H <= n-1; ++H)
    f[i][j][0] += f[i-1][H][1];

//注意，i个数中，选第j大的以后，还剩i-1个数，则原本第j+1大的变成第j大的，原本第i大的变成第i-1大的。

/*所以，i个数中，选第j大的以后，再往高里取（再下一个是只能往低里取的），方案数就是：

在i-1个数中

    选第j大以后往低里取的方案数
+ 选第j+1大以后往低里取的方案数
……
+ 选第i-1大以后往低里取的方案数
*/

(2)“往低里取”。则下一个必是山谷，又不得不往高里取。一模一样！

for(int H = 1; H < j; ++H)
    f[i][j][1] += f[i-1][H][0];

可见，如果有 f[i-1]，则 f[i] 可以推出来。所以是逆推的。

核心代码

f[1][1][0] = f[1][1][1] = 1;
for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
    {
        for(int H = j; H <= n-1; ++H)
            f[i][j][0] += f[i-1][H][1];

        for(int H = 1; H < j; ++H)
            f[i][j][1] += f[i-1][H][0];     
    }

int ans = 0;
for(int i = 1; i <= n; ++i)
    ans += f[n][i][1] + f[n][i][0], ans %= p;   

End~

个鬼啊，时间爆炸 n^3，空间爆炸 2n^2（4200 × 4200 × 2 × 4 B = 134.6MB），另外输入n=1时发现答案错误，咳咳。

首先，f[i] 只由 f[i-1] 推导，且最后只要用 f[n] 求答案。所以开 f[2][4201][2] 就好了，第一维滚动起来（f[flag] 只由 f[!flag] 推导）。

第二，手动模拟时很容易发现