题目链接：uva 10581 - Partitioning
for fun and profit

题目大意：给定m，n，k，将m分解成n份，然后依照每份的个数排定字典序，而且划分时要求ai−1≤ai，然后输出字典序排在k位的划分方法。

解题思路：由于有ai−1≤ai的条件。所以先记忆化搜索处理出组合情况dp[i][j][s]表示第i位为j。而且剩余的未划分数为s的总数为dp[i][j][s],然后就是枚举每一位上的值。推断序列的位置就可以。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 220;

const int maxp = 10;

int M, N;

ll K, dp[maxp+5][maxn+5][maxn+5];

ll dfs (int d, int x, int s) {

    if (d == N) {

        if (0 == s)

            return 1;

        else

            return 0;

    }

    ll& ans = dp[d][x][s];

    if (ans != -1)

        return ans;

    ans = 0;

    for (int i = x; ; i++) {

        if ((N-d) * i > s)

            break;

        ans += dfs(d+1, i, s-i);

    }

    return ans;

}

void solve () {

    int s = M, t = 1;

    for (int i = 1; i < N; i++) {

        for (int j = t; ; j++) {

            ll u = dp[i][j][s-j];

            if (K > u) {

                K -= u;

            } else {

                printf("%d\n", j);

                s -= j;

                t = j;

                break;

            }

        }

    }

    printf("%d\n", s);

}

int main () {

    int cas;

    scanf("%d", &cas);

    while (cas--) {

        scanf("%d%d%lld", &M, &N, &K);

        memset(dp, -1, sizeof(dp));

        for (int i = 1; i * N <= M; i++)

            ll u = dfs(1, i, M-i);

        solve();

    }

    return 0;

}