【01背包】HDU5656CA Loves GCD

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5656

  
  

   
   2
2
2 4
3
1 2 3
  
  

  
  

   
   8
10
  
  
  
  


  
  

  
  

   
   2
2
2 4
3
1 2 3
  
  

  
  

   
   8
10
  
  
  
  


  
  

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int mod=100000007;
const int inf=1<<29;
int a[1010],dp[1010][1010];
int g[1010][1010];
int n;
int gcd(int a,int b)
{
    if(a<b) swap(a,b);
    return !b?a:gcd(b,a%b);
}
void init()
{
    for(int i=0;i<=1000;i++){
        for(int j=0;j<=1000;j++){
            g[i][j]=g[j][i]=gcd(i,j);
        }
    }
}
int main()
{
    int t;
    init();
    cin>>t;
    while(t--){
       cin>>n;
       int V=-inf;
       memset(dp,0,sizeof(dp));
       dp[0][0]=1;
       for(int i=1;i<=n;i++) cin>>a[i],V=max(V,a[i]);       //  用V保存n个数中最大的数，最大公约数不可能大于V；
       for(int i=1;i<=n;i++){               //  枚举每个数；
           for(int j=0;j<=V;j++){           //  枚举可能存在的公约数；
               dp[i][j]+=dp[i-1][j];            //  不取；
               dp[i][j]%=mod;
               //if(dp[i-1][j]){              //  剪枝优化不会TLE；
                    int temp=g[a[i]][j];      //  打表更好；
                    //int temp=gcd(a[i],j);
                    dp[i][temp]+=dp[i-1][j];  //  取；
                    dp[i][temp]%=mod;
               //}
           }
       }
       long long ans=0;
       for(int i=1;i<=V;i++){
            //  orz....这里需要特别的注意啊，得转化成long long型在乘。。。WA了n次；
            ans+=(long long)dp[n][i]*i;        //  dp[n][i]记录的是公约数为i的个数，
            ans%=mod;
       }
       cout<<ans<<endl;
    }
    return 0;
}
/*
    题目意思：
        t，表示t组测试数据；
        n，表示有n个数；
        输入n个数,a[i];
        叫你求n个数所有子集的公约数之和；
    这是个01背包的题目；这种类型的背包题目可以总结为一种方案数的背包问题；
    就是给你n个数，组合成不同方案的方案数；
        1000*1000的数据量，还有gcd，不做任何优化的话TLE...
        这里我们有两个优化的方案；
        第一：就是我们可以事先打表出gcd(i,j);
        第二：增加剪枝，if(dp[i-1][j]) 我们就没有必要算gcd()了；
*/

   
   

    
    2
2
2 4
3
1 2 3
   
   

   
   

    
    8
10
   
   
   
   


   
   

最后

以上就是冷傲可乐为你收集整理的【01背包】HDU5656CA Loves GCD的全部内容，希望文章能够帮你解决【01背包】HDU5656CA Loves GCD所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。