首页 > 代码库 > UVA10128 - Queue(dp)

UVA10128 - Queue(dp)

UVA10128 - Queue(dp)

题目链接

题目大意:有N个人,通过排序,可以使得从前面往后面看只有P个人,从后面往前面看,只有R个人。问这样的排列有多少种。

解题思路:之前一直在要想怎么排序,结果是方法没找好,看了别人的题接后才发现应该把高个子的先排好,然后再把矮个子的插进去,这样对于从前往后看,还是从后往前看才有规律可循。假设n - 1个人已经排好对了,现在要排第n个人,这个人比之前的n - 1个人都要矮,这样我们就可以有三种排法:(1)、排在最前面那么前面看的就多了一个人;(2)排在对尾,那么从后面看的就多了一个人。(3)排在n个人的(n- 2)个间隙中的任何一个。那么前面看还是后面看都不会改变人数。
递推式:dp[n][p][r] = (n - 2)?dp[n - 1][p][r] + dp[n - 1][p - 1][r] + dp[n - 1][p][r - 1];

代码:

#include <cstdio>
#include <cstring>

typedef long long ll;
const int maxn = 15;

ll f[maxn][maxn][maxn];

int main () {

    int T;
    int N, P, R;
    scanf ("%d", &T);
    while (T--) {

        memset (f, 0, sizeof (f));
        scanf ("%d%d%d"    , &N, &P, &R);

        f[1][1][1] = 1;
        for (int i = 2; i <= N; i++)
            for (int j = 1; j <= i; j++)
                for (int k = 1; k <= i; k++) {
                    f[i][j][k] = (i - 2) * f[i - 1][j][k] + f[i - 1][j - 1][k] + f[i - 1][j][k - 1];        
                }
        printf ("%lld\n", f[N][P][R]);
    }
    return 0;
}

UVA10128 - Queue(dp)