UVALive - 6912 Prime Switch （状压DP）-白红宇

UVALive - 6912 Prime Switch （状压DP）

阅读量：7097 次

发布时间：2019-06-28

本文共 868 字，大约阅读时间需要 2 分钟。

题目链接：

【题意】有n个灯，m个开关，灯的编号从1~n,每个开关上有一个质数，这个开关同时控制编号为这个质数的倍数的灯，问最多有多少灯打开。

【分析】发现小于根号1000的质数有10个左右，然后大于根号1000的质数所控制的灯是不会重叠的，所以我们状压枚举小于31的质数，然后贪心后面的。

#include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)#define pb push_back#define mp make_pair#define rep(i,l,r) for(int i=(l);i<=(r);++i)#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int N = 1050;;const int M = 165;const int mod = 19260817;const int mo=123;const double pi= acos(-1.0);typedef pair
                
                 pii;int n,k,cas,cnt;int a[N],b[20];int vis[N];int main(){ int T; scanf("%d",&T); while(T--){ cnt=0; scanf("%d%d",&n,&k); for(int i=0;i

转载于:https://www.cnblogs.com/jianrenfang/p/7616957.html

你可能感兴趣的文章