uva 10581 - Partitioning for fun and profit(기억화 검색 + 수론)

6290 단어
제목 링크: uva 10581 - Partitioning for fun and profit
제목 대의: m, n, k를 정하고 m를 n부로 분해한 후 매 부의 개수에 따라 사전 서열을 정하고 구분할 때ai-1≤ai를 요구하며 사전 서열을 k위에 배열하는 구분 방법을 출력한다.
문제풀이 사고방식:ai-3-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
"
, j); s -= j; t = j; break; } } } printf("%d
"
, 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; }

좋은 웹페이지 즐겨찾기