Tak and Cards(DP,二维背包)

问题 K: Tak and Cards

时间限制: 1 Sec   内存限制: 128 MB
提交: 107   解决: 34
[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

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.

题意:给出n个数,从其中至少拿一个,使得平均数为k的拿法有多少种?

题解:dp[i][j]代表拿i个物品和为j的拿法,很明显状态转移方程可以为dp[j][kk]+=dp[j-1][kk-a[i]];必须倒着进行,否则就变成完全背包了。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#define gcd(a,b) __gcd(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FAST_IO ios::sync_with_stdio(false)
#define mem(a,b) memset(a,b,sizeof(a))
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const long long INF=0x7FFFFFFFFFFFFFFFLL;
const int inf=0x3f3f3f3f;
const unsigned long long mod=2000000000000000003;
typedef unsigned long long ll;
using namespace std;

int a[105];
ll dp[55][3005];
int main()
{
    int n,k;
    cin>>n>>k;

    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    ll tot=0;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        tot+=a[i];
        for(int j=i;j>=1;j--)
            for(int kk=tot;kk>=a[i];kk--)
                dp[j][kk]+=dp[j-1][kk-a[i]];
    }

    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=dp[i][i*k];

    printf("%lld\n",ans);
    return 0;
}