POJ3590 The shuffle Problem 置换+DP | DFS

  题目链接:http://poj.org/problem?id=3590

  自己暴力给水过去了,不过效率有点低。题目要求的就是给一个数n,要你求出一种方案,一些和为n的数的最小公倍数最大。题目数据量不大,容易想到用暴力的办法求出所用情况,然后比较就可以了,然后再剪下枝就可以过了。不过有更好的方法。和为n的数的最大公倍数可以用DP求出来:f[i][j]表示和为i的数划分为j个循环节时的最大公倍数,则f[i][j]=max{f[i-k][j-1] | j-1<=k<i-1};然后就是求最小的置换了。设n的最大公倍数是m,则有p1^k1*p2^k2*……*pn^kn=m,显然有p1^k1+p2^k2+……+pn^kn<=n,所以p1^k1,p2^k2,……,pn^kn就是每个循环的长度,然后贪心排一下就可以了,注意如果还有剩余,则按循环长度1计算。

 置换+DP:

 1 //STATUS:C++_AC_32MS_236KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 using namespace std;
13 #define LL __int64
14 #define pdi pair<int,int>
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int N=110,INF=0x3f3f3f3f,MOD=100000000;
21 const double DNF=100000000000;
22 
23 int f[N][N],list[N][N],one[N];
24 int n,k,T;
25 
26 int gcd(int a,int b)
27 {
28     return b?gcd(b,a%b):a;
29 }
30 
31 void getans(int a)
32 {
33     int i,k=0,cou,sum=n;
34     for(i=2;i<=a;i++){
35         if(a%i==0){
36             list[n][++k]=1;
37             while(a%i==0){
38                 list[n][k]*=i;
39                 a/=i;
40             }
41             sum-=list[n][k];
42         }
43     }
44     if(a>1)sum-=list[n][++k]=a;
45     sort(list[n],list[n]+k+1);
46     list[n][0]=k;
47     one[n]=sum;
48 }
49 
50 int main()
51 {
52  //   freopen("in.txt","r",stdin);
53     int i,j,t;
54     f[1][0]=f[1][1]=1;
55     for(i=2;i<=100;i++){
56         f[i][0]=f[i][1]=i;
57         for(j=2;j<=i;j++){
58             for(k=i-1;k>=j-1;k--)
59                 f[i][j]=Max(f[i][j],f[k][j-1]/gcd(f[k][j-1],i-k)*(i-k));
60             f[i][0]=Max(f[i][0],f[i][j]);
61         }
62     }
63     scanf("%d",&T);
64     while(T--)
65     {
66         scanf("%d",&n);
67         if(!list[n][0])getans(f[n][0]);
68         printf("%d",f[n][0]);
69         for(i=1;i<=one[n];i++)
70             printf(" %d",i);
71         t=one[n]+1;
72         for(i=1;i<=list[n][0];i++){
73             for(j=1;j<list[n][i];j++)
74                 printf(" %d",j+t);
75             printf(" %d",t);
76             t+=list[n][i];
77         }
78         putchar('\n');
79     }
80     return 0;
81 }

DFS:

 1 //STATUS:C++_AC_954MS_192KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 using namespace std;
13 #define LL __int64
14 #define pdi pair<int,int>
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int N=110,INF=0x3f3f3f3f,MOD=100000000;
21 const double DNF=100000000000;
22 
23 int A[N],list[N][N],ans[N],one[N];
24 int n,k,T;
25 
26 int gcd(int a,int b)
27 {
28     return b?gcd(b,a%b):a;
29 }
30 
31 void dfs(int cur,int val,int la)
32 {
33     if(val<=la){
34         int j,t=A[1],sum=n-A[1];
35         if(A[1]==1)sum++;
36         for(j=2;j<cur;j++){
37             sum-=A[j];
38             t=t/gcd(t,A[j])*A[j];
39         }
40         if( t>ans[n] || (t==ans[n] && sum>one[n]) ){
41             ans[n]=t;
42             for(j=1;j<cur;j++)list[n][j]=A[j];
43             list[n][0]=cur-1;
44             one[n]=sum;
45         }
46         return;
47     }
48     int i;
49     for(i=la+1;i<=val && i<=23;i++){
50         A[cur]=i;
51         dfs(cur+1,val-i,i);
52     }
53 }
54 
55 int main()
56 {
57  //   freopen("in.txt","r",stdin);
58     int i,j,t;
59     scanf("%d",&T);
60     while(T--)
61     {
62         scanf("%d",&n);
63         if(!list[n][0])dfs(1,n,0);
64         printf("%d",ans[n]);
65         if(one[n]){
66             t=one[n]+1;
67             for(i=1;i<=one[n];i++)printf(" %d",i);
68         }
69         else t=1;
70         for(i=1;i<=list[n][0];i++){
71             if(list[n][i]==1)continue;
72             for(j=1;j<list[n][i];j++)
73                 printf(" %d",t+j);
74             printf(" %d",t);
75             t+=list[n][i];
76         }
77         putchar('\n');
78     }
79     return 0;
80 }
原文地址:https://www.cnblogs.com/zhsl/p/2943512.html