首页 > 代码库 > UVA 12105 - Bigger is Better(DP+高精度)
UVA 12105 - Bigger is Better(DP+高精度)
题目链接:12105 - Bigger is Better
题意:一些火柴,问你能组成整除m最大的数字是多少。
思路:dp[i][j]表示用i根火柴,组成%m余数为j的最大数字,末尾多一个数字k的状态就是dp[i + num[k]][(j * 10 + k) % m],由于最多可能50位数,所以要用高精度。
注意一个优化点,由于高精度的计算上只需要乘10+k,常规的高精度乘法复杂度还是有点高会超时,所以用数组去模拟,每次*10 + k的时候就往后多一位即可。
代码:
#include <stdio.h> #include <string.h> const int N = 105; const int M = 3005; const int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; int n, m; char dp[N][M][55], ans[55], tmp[55]; void init() { scanf("%d", &m); memset(dp, 0, sizeof(dp)); memset(ans, 0, sizeof(ans)); dp[0][0][0] = ‘0‘; } int numcmp(char *a, char *b) { int lena = strlen(a); int lenb = strlen(b); if (lena < lenb) return -1; if (lena > lenb) return 1; return strcmp(a, b); } void DP(char *a, char *b, int k) { memset(tmp, 0, sizeof(tmp)); strcpy(tmp, b); int len = strlen(b); if (tmp[0] == ‘0‘) tmp[0] = ‘0‘ + k; else tmp[len] = ‘0‘ + k; if (numcmp(a, tmp) < 0) strcpy(a, tmp); } int main() { int cas = 0; while (~scanf("%d", &n) && n) { init(); for (int i = 0; i <= n; i++) { for (int j = 0; j < m; j++) { if (strlen(dp[i][j]) == 0) continue; for (int k = 0; k < 10; k++) { if (i + num[k] > n) continue; DP(dp[i + num[k]][(j * 10 + k) % m], dp[i][j], k); } } if (i != 0 && numcmp(ans, dp[i][0]) < 0) strcpy(ans, dp[i][0]); } printf("Case %d: ", ++cas); if (ans[0] == 0) printf("-1\n"); else printf("%s\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。