首页 > 代码库 > HDU 5902 GCD is Funny DP
HDU 5902 GCD is Funny DP
http://acm.hdu.edu.cn/showproblem.php?pid=5902
一眼看上去，以为是枚举两个数，然后去重gcd即可。
但是不是
6 6 10 15这样的数据
应该是1 2 3 5 6
1是从6 6 15得到gcd = 3，然后3和10搭配得到的。
那么就是其它的gcd能够作为新的数字，去枚举其他数字，得到其他gcd。其实这个应该很容易想到的，但是比赛的时候却认为只用枚举两个就够了，可能是因为1001，觉得应该是水题吧。其实是自己蔡。。
那么考虑dp。
dp[i][val]表示在前i个数中，能否得到val这个值。
这是一个类似背包的问题了
先预处理出任意两个的所得到的gcd值。
然后枚举每个a[i]来加入前i - 1个数，对于出现过的，dp[i][j]也能出现，一直传递上去即可。
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>int n;const int maxn = 1000 + 20;int a[maxn];int gcd(int n, int m) { if (n % m == 0) { return m; } else return gcd(m, n%m);}bool dp[maxn][maxn];//int index;void work() {// ++index; memset(dp, 0, sizeof dp); int mx = -inf; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); mx = max(mx, a[i]); } for (int i = 2; i <= n; ++i) { for (int j = 1; j < i; ++j) { dp[i][gcd(a[i], a[j])] = 1; } } for (int i = 3; i <= n; ++i) { for (int j = 1; j <= mx; ++j) { if (dp[i - 1][j]) { dp[i][j] = 1; dp[i][gcd(j, a[i])] = 1; } } } bool flag = false; for (int i = 1; i <= mx; ++i) { if (dp[n][i]) { if (flag) { printf(" %d", i); } else { printf("%d", i); flag = true; } } } printf("\n");}int main() {#ifdef local freopen("data.txt","r",stdin);#endif int t; scanf("%d", &t); while(t--) { work(); } return 0;}
不memset好像更快
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>int n;const int maxn = 1000 + 20;int a[maxn];int gcd(int n, int m) { if (n % m == 0) { return m; } else return gcd(m, n%m);}int dp[maxn][maxn];int index;void work() { ++index;// memset(dp, 0, sizeof dp); int mx = -inf; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); mx = max(mx, a[i]); } for (int i = 2; i <= n; ++i) { for (int j = 1; j < i; ++j) { dp[i][gcd(a[i], a[j])] = index; } } for (int i = 3; i <= n; ++i) { for (int j = 1; j <= mx; ++j) { if (dp[i - 1][j] == index) { dp[i][j] = index; dp[i][gcd(j, a[i])] = index; } } } bool flag = false; for (int i = 1; i <= mx; ++i) { if (dp[n][i] == index) { if (flag) { printf(" %d", i); } else { printf("%d", i); flag = true; } } } printf("\n");}int main() {#ifdef local freopen("data.txt","r",stdin);#endif int t; scanf("%d", &t); while(t--) { work(); } return 0;}
HDU 5902 GCD is Funny DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。