首页 > 代码库 > D - 稳住GCD DP

D - 稳住GCD DP

2024-08-14 15:46:03   210人阅读

http://acm.uestc.edu.cn/#/problem/show/923

给定一堆数字，求其所有数字的gcd。

现在要删除最多的数字，使得剩下的数字的gcd和原来的一样。

设dp[i][val]表示在前i个数中，得到val这个数字所需的最小数字，怎么得到val这个数字？就是gcd得到。

dp[i][gcd]

然后转移就是

dp[i][a[i]] = 1是必然的，自己一个

枚举新数字得到新的gcd  val

dp[i][val] = min(dp[i][val], dp[i - 1][j]  + 1)

每次都要和自己比较一下，因为防止自己更小，就是dp[i][val]本来就是1，这样就不需要枚举其他数加入来了，。

技术分享
//#include<stdio.h>//int main() {//    int i;//    char a[10][3]= {"一","和","三","四","物","社","嗯","阶","己","嗯"};//    for(i=0; i<10; i++)//        printf("%s\n",a[i]);//    return 0;//}#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 dp[700 + 20][10000 + 20];int a[10000 + 20];void work() {    int n;    cin >> n;    for (int i = 1; i <= n; ++i) {        cin >> a[i];    }    int ans = a[1];    for (int i = 2; i <= n; ++i) {        ans = __gcd(ans, a[i]);    }    memset(dp, 0x3f, sizeof dp);    dp[1][a[1]] = 1;    for (int i = 2; i <= n; ++i) {        dp[i][a[i]] = 1; //自己一直出现，一次就够        for (int j = 1; j <= 10000; ++j) {            if (dp[i - 1][j] != inf) {                dp[i][j] = min(dp[i][j], dp[i - 1][j]);                int t = __gcd(j, a[i]);                dp[i][t] = min(dp[i][t], dp[i - 1][j] + 1);            }        }    }    cout << n - dp[n][ans] << endl;}int main() {#ifdef local    freopen("data.txt","r",stdin);#endif    work();    return 0;}
View Code

 

D - 稳住GCD DP


联系
我们