UVA 10581 - Partitioning for fun and profit

1881 단어 partition

10581 - Partitioning for fun and profit


제목 링크
제목: m, n을 정하여 n개의 칸에 분배하고 m개의 숫자를 분배하여 각각 칸마다 최소한 1을 넣는다. 그리고 서열이 점차적으로 증가하면 k개의 사전 서열이 무엇인지 묻는다.
사고방식: 먼저 dp를 이용하여 표를 작성하고 dp[i][j][k]는 i의 개수를 표시하며 꼬리는 j이고 나머지 k의 상황을 합쳐서 하나의 기억화로 구한다. 그 다음에 이 수조를 바탕으로 왼쪽에서 오른쪽으로 열거할 때 그 숫자를 적당히 넣고 출력한다. 마지막 숫자는 단독으로 출력해야 한다.
코드:
#include <cstdio>
#include <cstring>

typedef long long LL;
int t, M, n, vis[15][225][225];
LL k, dp[15][225][225];

LL DP(int now, int tail, int m) {
    LL &ans = dp[now][tail][m];
    if (vis[now][tail][m]) return ans;
    vis[now][tail][m] = 1;
    ans = 0;
    if (now == n) return ans = 1;
    if (now == n - 1) {
	if (m >= tail)
	    return ans = DP(now + 1, m, 0);
	return ans = 0;
    }
    for (int i = tail; i <= m - (n - now - 1); i++)
	ans += DP(now + 1, i, m - i);
    return ans;
}

void solve(LL k) {
    int v = 1;
    for (int i = 1; i < n; i++) {
	for (int j = v; j <= M - (n - i); j++) {
	    if (k > dp[i][j][M - j]) k -= dp[i][j][M - j];
	    else {
		M -= j;
		v = j;
		printf("%d
", j);
		break;
	    }
	}
    }
    printf("%d
", M);
}

int main() {
    scanf("%d", &t);
    while (t--) {
	memset(vis, 0, sizeof(vis));
	scanf("%d%d%lld", &M, &n, &k);
	DP(0, 1, M);
	solve(k);
    }
    return 0;
}
uva 10271 Chopsticks(dp)
[noip2013] 꽃장인DP||욕심

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage