Tak and Cards dp

6461: Tak and Cards

时间限制: 1 Sec  内存限制: 128 MB
提交: 142  解决: 51
[提交][状态][讨论版][命题人: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.

题意：求一串数字中不连续子串使其总和是a的倍数

动态规划求解，因为数据范围小，所以从小到大枚举计算，最后找出倍数

i代表相加的数的个数，j代表相加得到该数的方案数

#include 
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int INF=55;
ll dp[INF][INF*INF]; //防止爆int
int main()
{int n,a;cin>>n>>a;int x;dp[0][0]=1;for(int i=1; i<=n; i++){cin>>x;for(int j=i-1; j>=0; j--){for(int k=0; k<=INF*j; k++){   dp[j+1][k+x]+=dp[j][k];}}}ll ans=0;for(int i=1; i<=n; i++){ans+=dp[i][i*a];}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！