Tak and Cards（dp 背包）

Tak and Cards

时间限制: 1 Sec  内存限制: 128 MB

题目描述

Tak has N cards. On the i-th (1≤i≤N) card is written an integer xi. He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A. In how many ways can he make his selection?

Constraints
1≤N≤50
1≤A≤50
1≤xi≤50
N,A,xi are integers.
Partial Score
200 points will be awarded for passing the test set satisfying 1≤N≤16.

输入

The input is given from Standard Input in the following format:
N A
x1 x2 … xN

输出

Print the number of ways to select cards such that the average of the written integers is exactly A.

样例输入

4 8

7 9 8 9

样例输出

5

提示

The following are the 5 ways to select cards such that the average is 8:
Select the 3-rd card.
Select the 1-st and 2-nd cards.
Select the 1-st and 4-th cards.
Select the 1-st, 2-nd and 3-rd cards.
Select the 1-st, 3-rd and 4-th cards.

来源

ABC044&ARC060 

Submit State

题意：给ｎ个数字，求这ｎ个数字平均数为ａ的组合数。

完全解要用背包来做，设dp(i,j,k)为在第i个数字前选j个，和为k的所有组合数目。由于我们知道平均数的计算方法为Σxi/X，设a=Σxi/X，则a*X=Σxi。我们最后只需要统计所有的dp(n,X,a*X)就行了。

转移的话首先计数要把之前的结果转移到当前结果下，dp(i,j,k)+=dp(i-1,j,k)。

接下来就是背包了，dp(i,j,k)+=dp(i-1,j-1,k-x(i-1)) | {k >= x(i-1)}

三维dp

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll dp[55][55][2550];
ll x[50];
int main()
{
    int n,a;
    scanf("%d%d",&n,&a);
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for (int i=0;i<n;i++)
        scanf("%lld",&x[i]);
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=i;j++)
        {
            for (int k=0;k<=2510;k++)
            {

                if (k>=x[i-1] && j>=1)
                    dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]]+dp[i-1][j][k];
                else
                    dp[i][j][k]+=dp[i-1][j][k];

            }
        }
    }
    ll ans=0;
    for (int i=1;i<=n;i++)
        ans+=dp[n][i][i*a];
    printf("%lld\n",ans);
    return 0;
}

二维dp

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
bool cmp(int x,int y)
{
    return x>y;
}
const int N=2e5+20;
const ll mod=1e9+7;
ll dp[105][10005];
int main()
{
    int n,a;
    int x;
    ll ans=0;
    ll now=0;
    dp[0][0]=1;
    scanf("%d%d",&n,&a);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        now+=x;
        for(int j=i;j>=1;j--)
        {
            for(int k=now;k>=x;k--)
            {
                dp[j][k]+=dp[j-1][k-x];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans+=dp[i][a*i];
    }
    printf("%lld\n",ans);
    return 0;
}