首页 > 代码库 > 6661 Equal Sum Sets（DP)

6661 Equal Sum Sets（DP)

2024-07-24 11:42:36   216人阅读

Let us consider sets of positive integers less than or equal to n. Note that all elements of a set are
different. Also note that the order of elements doesnt matter, that is, both {3, 5, 9} and {5, 9, 3} mean
the same set.
Specifying the number of set elements and their sum to be k and s, respectively, sets satisfying the
conditions are limited. When n = 9, k = 3 and s = 23, {6, 8, 9} is the only such set. There may be
more than one such set, in general, however. When n = 9, k = 3 and s = 22, both {5, 8, 9} and {6, 7, 9}
are possible.
You have to write a program that calculates the number of the sets that satisfy the given conditions.
Input
The input consists of multiple datasets. The number of datasets does not exceed 100.
Each of the datasets has three integers n, k and s in one line, separated by a space. You may assume
1 ≤ n ≤ 20, 1 ≤ k ≤ 10 and 1 ≤ s ≤ 155.
The end of the input is indicated by a line containing three zeros.
Output
The output for each dataset should be a line containing a single integer that gives the number of the
sets that satisfy the conditions. No other characters should appear in the output.
You can assume that the number of sets does not exceed 231 ? 1.
Sample Input
9 3 23
9 3 22
10 3 28
16 10 107
20 8 102
20 10 105
20 10 155
3 4 3
4 2 11
0 0 0
Sample Output
1
2
0
20
1542
5448
1
0

0


DP递推：dp[i][k][s]表示个数递推关系：dp[i][k][s]=dp[i-1][k][s]+dp[i-1][k-1][s-i].

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000+100;
int dp[21][11][156];
void init()
{
    memset(dp,0,sizeof(dp));
    dp[1][1][1]=1;
    for(int i=1;i<=20;i++)
    {
        dp[i][1][i]=1;
        dp[i][0][0]=1;
    }
    for(int i=2;i<=20;i++)
    {
        for(int k=1;k<=10;k++)
        {
            if(k>i)   continue;
            for(int s=1;s<=155;s++)
            {
                int sum=0;
//                for(int j=1;j<i&&j<=k;j++)
                    sum+=dp[i-1][k][s];
                if(s>=i) sum+=dp[i-1][k-1][s-i];
                dp[i][k][s]=sum;
//                if(i<=4&&s<10)
//                   cout<<i<<" "<<k<<" "<<s<<" "<<sum<<endl;
            }
        }
    }
//    cout<<dp[4][2][5]<<endl;
}
int main()
{
    init();
    int n,k,s;
    while(~scanf("%d%d%d",&n,&k,&s)&&(n+k+s))
        printf("%d\n",dp[n][k][s]);
    return 0;
}

另类似的HDU 2861 

Problem Description
Patti and Terri run a bar in which there are 15 stools. One day, Darrell entered the bar and found that the situation how customers chose the stools were as follows:
OOEOOOOEEEOOOEO
O means that the stool in a certain position is used, while E means that the stool in a certain position is empty (here what we care is not who sits on the stool, but whether the stool is empty).As the example we show above, we can say the situation how the 15 stools is used determines 7 intervals (as following):
OO E OOOO EEE OOO E O

Now we postulate that there are N stools and M customers, which make up K intervals. How many arrangements do you think will satisfy the condition?
 

Input
There are multi test cases and for each test case:
Each case contains three integers N (0<N<=200), M (M<=N), K (K<=20).
 

Output
For each test case print the number of arrangements as described above. (All answers is fit in 64-bit.)
 

Sample Input
3 1 3
4 2 4
 

Sample Output
1
2


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
typedef long long LL;
using namespace std;
LL dp[201][201][22][2];
void init()
{
    memset(dp,0,sizeof(dp));
    dp[1][0][1][0]=1;
    dp[1][1][1][1]=1;
    for(int i=1;i<=200;i++)
    {
        dp[i][0][1][0]=1;
        dp[i][i][1][1]=1;
    }
    for(int i=2;i<=200;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=1;k<=20&&k<=i;k++)
            {
                dp[i][j][k][0]=dp[i-1][j][k-1][1]+dp[i-1][j][k][0];
                dp[i][j][k][1]=dp[i-1][j-1][k][1]+dp[i-1][j-1][k-1][0];
            }
        }
    }
//    cout<<dp[12][13][15][0]<<endl;
}
int main()
{
    int n,m,k;
    init();
    while(~scanf("%d%d%d",&n,&m,&k))
        printf("%I64d\n",dp[n][m][k][0]+dp[n][m][k][1]);
    return 0;
}


6661 Equal Sum Sets（DP)


联系
我们