【noi 2.5_7834】分成互质组（dfs）

有2种dfs的方法：

1.存下每个组的各个数和其质因数，每次对于新的一个数，与各组比对是否互质，再添加或不添加入该组。

2.不存质因数了，直接用gcd，更加快。P.S.然而我不知道为什么RE，若有好心人发现请教教我吧，谢谢~ :-)

下面附上方法1的AC代码——

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<cmath>

 5 #include<iostream>

 6 using namespace std;

 7

 8 int n,ans=12;

 9 int a[12];

10 struct node {int t;int p[3000];}

11 b[12];

12

13 int mmin(int x,int y)

14 {   return x<y?x:y;  }

15 int com(int id,int x)

16 {

17     for (int i=1;i<=b[id].t;i++)

18       if (x%b[id].p[i]==0) return 0;

19     return 1;

20 }

21 void dfs(int id,int h)

22 {

23     int x=a[id];

24     if (id>n) {ans=mmin(ans,h); return;}

25     for (int i=1;i<=h;i++)

26       if (com(i,x))

27       {

28         int y=x,tt=b[i].t;

29         for (int j=2;j<=y;j++)//sqrt(y) wrong

30           if (y%j==0) y/=j, b[i].p[++b[i].t]=j;

31         dfs(id+1,h);

32         b[i].t=tt;

33       }

34     int y=x;

35     b[h+1].t=0;

36     for (int j=2;j<=y;j++)

37       if (y%j==0) y/=j, b[h+1].p[++b[h+1].t]=j;

38     dfs(id+1,h+1);

39 }

40 int main()

41 {

42     scanf("%d",&n);

43     for (int i=1;i<=n;i++)

44       scanf("%d",&a[i]);

45     dfs(1,0);

46     printf("%d",ans);

47     return 0;

48 }

方法2的90分RE代码——

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6

 7 const int N=15;

 8 int n,ans;

 9 int a[N],b[N][N],t[N];

10

11 int mmin(int x,int y)

12 {   return x<y?x:y;  }

13 int gcd(int x,int y)

14 {   return (!y)?x:gcd(y,x%y);  }

15 bool addit(int x,int i)

16 {

17     for (int j=1;j<=t[i];j++)

18       if (gcd(x,b[i][j])!=1) return false;

19     return true;

20 }

21 void dfs(int x,int h)

22 {

23     if (x>n) {ans=mmin(h,ans);return;}

24     for (int i=1;i<=h;i++)

25       if (addit(a[x],i))

26       {

27         b[i][++t[i]]=a[x];

28         dfs(x+1,h);

29         t[i]--;

30       }

31     b[h+1][++t[h+1]]=a[x];

32     dfs(x+1,h+1);

33 }

34 int main()

35 {

36     scanf("%d",&n);

37     for (int i=1;i<=n;i++)

38       scanf("%d",&a[i]);

39     memset(t,0,sizeof(t));

40     ans=N;

41     dfs(1,0);

42     printf("%d\n",ans);

43     return 0;

44 }

其实noi上的数据还有个问题——1应该专门放在一组中，而该题数据没有考虑到这点......

巴特西

【noi 2.5_7834】分成互质组（dfs）

最新文章

热门文章