首页 > 代码库 > UVA 10581 - Partitioning for fun and profit(数论递推)
UVA 10581 - Partitioning for fun and profit(数论递推)
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\n", j); break; } } } printf("%d\n", 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。