UvaLive6661 Equal Sum Sets dfs或dp

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

题解：

DFS或者DP或打表。

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

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define ll __int64

 #define usint unsigned int

 #define mz(array) memset(array, 0, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(int i=0;i<(n);i++)

 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("D.in","r",stdin)

 #define WE  freopen("1biao.out","w",stdout)

 const int maxn=;

 bool h[maxn];

 int ans;

 int n,k,s;

 void dfs(int x,int sum,int start) {

     if(sum>s) return;

     if(x==k) {

         if(sum==s) ans++;

         return;

     }

     for(int i=start; i<=n; i++) {

         if(h[i]==false) {

             h[i]=true;

             dfs(x+,sum+i,i+);

             h[i]=false;

         }

     }

     return;

 }

 int farm() {

     memset(h,,sizeof(h));

     ans=;

     dfs(,,);

     return ans;

 }

 int main() {

     while(scanf("%d%d%d",&n,&k,&s)!=EOF) {

         if(n== && k== && s==) break;

         //cout<<n<<','<<k<<','<<s<<endl;

         printf("%d\n",farm());

     }

     return ;

 }

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的种类。

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define ll __int64

 #define usint unsigned int

 #define mz(array) memset(array, 0, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(int i=0;i<(n);i++)

 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("D.in","r",stdin)

 #define WE  freopen("1biao.out","w",stdout)

 int n,k,s;

 int dp[][][];

 int main() {

     int i,j,k;

     int maxj;

     mz(dp);

     dp[][][]=;

     for(i=; i<=; i++) {

         for(k=; k<=; k++) {

             dp[i][k][]=dp[i-][k][];

             maxj=(i+i-k+)*k/;///此i和k能打到的最大的j

             for(j=; j<=maxj; j++) {///dp[i][k][j]，用数1~i中的k个组成j的种类数

                 dp[i][k][j]=dp[i-][k][j];///继承

                 if(j>=i) dp[i][k][j] += dp[i-][k-][j-i];///没i的状态加上i

             }

         }

     }

     while(scanf("%d%d%d",&n,&k,&s)!=EOF) {

         if(n== && k== && s==) break;

         //cout<<n<<','<<k<<','<<s<<endl;

         printf("%d\n",dp[n][k][s]);

     }

     return ;

 }

3.DP 空间降一维

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

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

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define ll __int64

 #define usint unsigned int

 #define mz(array) memset(array, 0, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(int i=0;i<(n);i++)

 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("D.in","r",stdin)

 #define WE  freopen("1biao.out","w",stdout)

 int n,K,s;

 int dp[][];

 int main() {

     int i,j,k;

     int maxj;

     while(scanf("%d%d%d",&n,&K,&s)!=EOF) {

         if(n== && K== && s==) break;

         mz(dp);

         dp[][]=;

         for(i=; i<=n; i++) {///用1到i中的数

             for(k=K; k>; k--) {

                 for(j=i; j<=s; j++) {///dp[k][j]，k个数组成数j的种类数

                     dp[k][j] += dp[k-][j-i];///没i的状态加上i

                 }

             }

         }

         printf("%d\n",dp[K][s]);

     }

     return ;

 }

4.打表

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

（代码太长了贴不上来）

巴特西

UvaLive6661 Equal Sum Sets dfs或dp

最新文章

热门文章