• 欢迎光临~

SP15637 GNYR04H - Mr Youngs Picture Permutations

开发技术 开发技术 2022-11-01 次浏览

SP15637 GNYR04H - Mr Youngs Picture Permutations - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

好题。

考虑从小到大(身高从高到低)安排每个数的位置。

这样,已经被安排的数在每一行肯定占据了最左端连续的一段。否则假设某个人 (A) 左面有个空位,这个空位后来被 (B) 补齐,由于我们从小到大考虑数,因此 (A < B),然而 (A) 却在 (B) 的右方,这显然是不合法的。

同理,我们每安排一个数肯定是把它追加到某一行最左侧连续一段的右侧。因此整个过程相当于五行从左到右的填数。

再思考一下从上到下递增这个制约条件。我们发现,如果填数在第一行,那不用管。否则,因为仍然是从小到大填数,所以我们只要保证填这个数 (B) 的时候上方有一个数 (A) 即可,由于 (A < B),单调性得以满足。而如果上面还没有数,之后上面才被一个数 (C) 补齐,就一定不行,因为 (C > B),失去单调性。

同时我们还需要保证每一行的人数不会超限。

考虑 dp,因为个人喜好选择刷表法。

(now = f(a_1, a_2, a_3, a_4, a_5)) 表示第一行被放置了 (a_1) 个数,第二行被放置了 (a_2) 个数……第五行被放置了 (a_5) 个数时的方案。

我们考虑下一个数是否可以被安排在第 (i) 行。有以下两个条件:

  • (a_i + 1 le n_i)(不可以超限);
  • (i = 1 or a_i + 1 le a_{i - 1})(填这个数时上面必须有数,或者本来就在第一行);

如果满足这个条件,就可以给 (f(a_1, cdots, a_i +1, cdots, a_5)) 给出 (now) 的贡献。

时间复杂度 (mathcal{O}(n^k))

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-11-01 01:57:22 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-11-01 02:29:34
 */

#include <bits/stdc++.h>
inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}


const int maxn = 30;
unsigned f[maxn][maxn][maxn][maxn][maxn];
int a[7];

int main() {
    int n = 0;

    while ((n = read()) && n) {
        std :: memset(f, 0, sizeof(f));
        std :: memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; ++i)
            a[i] = read();

        f[0][0][0][0][0] = 1;
        for (int x1 = 0; x1 <= a[1]; ++x1)
        for (int x2 = 0; x2 <= a[2]; ++x2)
        for (int x3 = 0; x3 <= a[3]; ++x3)
        for (int x4 = 0; x4 <= a[4]; ++x4)
        for (int x5 = 0; x5 <= a[5]; ++x5) {
            int now = f[x1][x2][x3][x4][x5];
            if (x1 < a[1])
                f[x1 + 1][x2][x3][x4][x5] += now;
            if (x2 < a[2] && x2 < x1)
                f[x1][x2 + 1][x3][x4][x5] += now;
            if (x3 < a[3] && x3 < x2)
                f[x1][x2][x3 + 1][x4][x5] += now;
            if (x4 < a[4] && x4 < x3)
                f[x1][x2][x3][x4 + 1][x5] += now;
            if (x5 < a[5] && x5 < x4)
                f[x1][x2][x3][x4][x5 + 1] += now;
        }

        printf("%un", f[a[1]][a[2]][a[3]][a[4]][a[5]]);
    }

    return 0;
}
程序员灯塔
转载请注明原文链接:SP15637 GNYR04H - Mr Youngs Picture Permutations
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com