题目

Source

http://acm.hdu.edu.cn/showproblem.php?pid=5800

Description

Dear Guo

I never forget the moment I met with you.You carefully asked me: "I have a very difficult problem. Can you teach me?".I replied with a smile, "of course"."I have n items, their weight was a[i]",you said,"Let's define f(i,j,k,l,m) to be the number of the subset of the weight of n items was m in total and has No.i and No.j items without No.k and No.l items.""And then," I asked.You said:"I want to know

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}\sum_{m=1}^{s}f(i,j,k,l,m)\quad (i,j,k,l\quad are\quad different)$$

Sincerely yours,
Liao

Input

The first line of input contains an integer T(T≤15) indicating the number of test cases.
Each case contains 2 integers n, s (4≤n≤1000,1≤s≤1000). The next line contains n numbers: a1,a2,…,an (1≤ai≤1000).

Output

Each case print the only number — the number of her would modulo 109+7 (both Liao and Guo like the number).

Sample Input

2
4 4
1 2 3 4
4 4
1 2 3 4

Sample Output

8
8

分析

题目大概就是说给n个数和s，然后求上面那个式子的结果，f(i,j,k,l,m)表示下标i和j的数必选、k和l不选且选出数的和为s的选法总数。

dp[x][y][i][j]表示前i个数中选出总和为j且有x个数确定必选、y个数确定不选的方案数
转移就是选和不选从i到i+1转移，选可以向x或x+1转移，不选可以向y或y+1转移
最后的结果就是A(2,2)*A(2,2)*Σdp[2][2][n][0...s]

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int d[3][3][1111][1111];

int main(){

	int t,n,s,a;

	scanf("%d",&t);

	while(t--){

		scanf("%d%d",&n,&s);

		memset(d,0,sizeof(d));

		d[0][0][0][0]=1;

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

			scanf("%d",&a);

			for(int j=0; j<=s; ++j){

				for(int x=0; x<3; ++x){

					for(int y=0; y<3; ++y){

						if(d[x][y][i][j]==0) continue;

						d[x][y][i+1][j]+=d[x][y][i][j];

						d[x][y][i+1][j]%=1000000007;

						if(y<2){

							d[x][y+1][i+1][j]+=d[x][y][i][j];

							d[x][y+1][i+1][j]%=1000000007;

						}

						if(j+a>s) continue;

						d[x][y][i+1][j+a]+=d[x][y][i][j];

						d[x][y][i+1][j+a]%=1000000007;

						if(x<2){

							d[x+1][y][i+1][j+a]+=d[x][y][i][j];

							d[x+1][y][i+1][j+a]%=1000000007;

						}

					}

				}

			}

		}

		long long ans=0;

		for(int i=0; i<=s; ++i){

			ans+=d[2][2][n][i];

			ans%=1000000007;

		}

		ans<<=2;

		ans%=1000000007;

		printf("%I64d\n",ans);

	}

	return 0;

}

巴特西

HDU5800 To My Girlfriend（DP）

题目