首页 > 代码库 > UvaLive6661 Equal Sum Sets dfs或dp

UvaLive6661 Equal Sum Sets dfs或dp

2024-07-16 13:24:06   217人阅读

UvaLive6661

PDF题目

题意：让你用1~n中k个不同的数组成s，求有多少种组法。

题解：

DFS或者DP或打表。

1.DFS 由于数据范围很小，直接dfs每种组法统计个数即可。

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll __int6414 #define usint unsigned int15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(int i=0;i<(n);i++)18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("D.in","r",stdin)24 #define WE  freopen("1biao.out","w",stdout)25 26 const int maxn=22;27 bool h[maxn];28 int ans;29 int n,k,s;30 void dfs(int x,int sum,int start) {31     if(sum>s) return;32     if(x==k) {33         if(sum==s) ans++;34         return;35     }36     for(int i=start; i<=n; i++) {37         if(h[i]==false) {38             h[i]=true;39             dfs(x+1,sum+i,i+1);40             h[i]=false;41         }42     }43     return;44 }45 46 int farm() {47     memset(h,0,sizeof(h));48     ans=0;49     dfs(0,0,1);50     return ans;51 }52 53 int main() {54     while(scanf("%d%d%d",&n,&k,&s)!=EOF) {55         if(n==0 && k==0 && s==0) break;56         //cout<<n<<‘,‘<<k<<‘,‘<<s<<endl;57         printf("%d\n",farm());58     }59     return 0;60 }
View Code

 

2.DP

dp[i][k][j]代表用1~i中的数中的k个组成j的种类数。

dp[i][k][j]=dp[i-1][k][j] + dp[i-1][k-1][j-i]，加号左边是继承1~i-1的种类数（因为1~i的种类数包括1~i-1的种类数），加号右边是给那些由k-1个数组成的种类加上i得到j的种类。

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll __int6414 #define usint unsigned int15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(int i=0;i<(n);i++)18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("D.in","r",stdin)24 #define WE  freopen("1biao.out","w",stdout)25 int n,k,s;26 int dp[33][22][166];27 28 int main() {29     int i,j,k;30     int maxj;31     mz(dp);32     dp[0][0][0]=1;33     for(i=1; i<=20; i++) {34         for(k=0; k<=10; k++) {35             dp[i][k][0]=dp[i-1][k][0];36             maxj=(i+i-k+1)*k/2;///此i和k能打到的最大的j37             for(j=1; j<=maxj; j++) {///dp[i][k][j]，用数1~i中的k个组成j的种类数38                 dp[i][k][j]=dp[i-1][k][j];///继承39                 if(j>=i) dp[i][k][j] += dp[i-1][k-1][j-i];///没i的状态加上i40             }41         }42     }43     while(scanf("%d%d%d",&n,&k,&s)!=EOF) {44         if(n==0 && k==0 && s==0) break;45         //cout<<n<<‘,‘<<k<<‘,‘<<s<<endl;46         printf("%d\n",dp[n][k][s]);47     }48     return 0;49 }
View Code

 

3.DP 空间降一维

dp[k][j]表示k个数组成j的种类数。

有一维要逆序for，防止同一i下重复计算。

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll __int6414 #define usint unsigned int15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(int i=0;i<(n);i++)18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("D.in","r",stdin)24 #define WE  freopen("1biao.out","w",stdout)25 int n,K,s;26 int dp[12][166];27 28 int main() {29     int i,j,k;30     int maxj;31     while(scanf("%d%d%d",&n,&K,&s)!=EOF) {32         if(n==0 && K==0 && s==0) break;33         mz(dp);34         dp[0][0]=1;35         for(i=1; i<=n; i++) {///用1到i中的数36             for(k=K; k>0; k--) {37                 for(j=i; j<=s; j++) {///dp[k][j]，k个数组成数j的种类数38                     dp[k][j] += dp[k-1][j-i];///没i的状态加上i39                 }40             }41         }42         printf("%d\n",dp[K][s]);43     }44     return 0;45 }
View Code

 

4.打表

深搜怕超时可以怒打一表，只要不限制代码长度就随便过。

（代码太长了贴不上来）

 


联系
我们