HDU 5800 To My Girlfriend 背包

题目链接：

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

To My Girlfriend

Time Limit: 2000/2000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)

问题描述

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

∑i=1n∑j=1n∑k=1n∑l=1n∑m=1sf(i,j,k,l,m)(i,j,k,laredifferent)

Sincerely yours,

Liao

输入

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).

输出

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

题意

问你所有和为k(0<=k<=s)，且两个元素（i,j）在其中，两个元素（l,m)不在其中的所有四元组。

题解

变种背包问题。

dp[i][j][s1]s2表示现在处理到第i个数，和为j且s1个元素必选，s2个元素必不选的的情况。

那么每个元素有四种情况：塞到s1里面、塞到s2里面、塞进来但不放在s1,s2、根本不塞进来。

最后的答案就是4*sigma(dp[n][k][2][2])。乘4是以为之前没有考虑(i,j),(l,m)内部的顺序。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1001;
typedef long long LL;

const int  mod = 1e9 + 7;

//开long long 的话就要用滚动数组了。
int dp[maxn][maxn][3][3];
int n, m;
int arr[maxn];

void add_mod(int &x, int y) {
	x = (x + y) % mod;
}

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
		memset(dp, 0, sizeof(dp));
		dp[0][0][0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				for (int s1 = 0; s1 < 3; s1++) {
					for (int s2 = 0; s2 < 3; s2++) {
						//不塞
						add_mod(dp[i][j][s1][s2], dp[i - 1][j][s1][s2]);
						//塞
						if (j >= arr[i]) add_mod(dp[i][j][s1][s2], dp[i - 1][j - arr[i]][s1][s2]);
						//塞进s1
						if (j >= arr[i]&&s1-1>=0) add_mod(dp[i][j][s1][s2], dp[i - 1][j - arr[i]][s1 - 1][s2]);
						//塞进s2
						if (s2 - 1 >= 0) add_mod(dp[i][j][s1][s2], dp[i - 1][j][s1][s2 - 1]);
					}
				}
			}
		}
		LL ans = 0;
		for (int i = 0; i <= m; i++) ans+=dp[n][i][2][2],ans%=mod;
		ans = 4 * ans%mod;
		printf("%lld\n", ans);
	}
	return 0;
}