2016-10-08

HDU 5800 To My Girlfriend【DP】

题目链接：

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

题意：

给定长度为$n$的序列，定义$f(i,j,k,l,m)$为集合个数，其中集合中必须含有$i,j$元素，不含有$l,m$元素，求$\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)$,

分析：

问题的关键是设计状态。
比较容易想到$n^3$的状态，而且其中考虑的元素个数和$m$那两维是必须有的，那么我们再引入两维，一维表示必须拿的个数，另一维为必须不拿的个数。
对于每一个元素有

必须有，放入集合中
必须没有，不放入集合中
可有可无，但是放入集合中
可有可无，不放入集合中

这样直接转移状态，时间复杂度$O(4 \times n^2)$。
由于$i,j$和$l,m$不同，最后答案要再乘上个$4$

代码：


#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e3 + 5, oo = 0x3f3f3f3f, mod = 1e9 + 7;
int dp[maxn][maxn][4][4];
int a[maxn];
int main (void)
{
	int T;scanf("%d", &T);
	while(T--){
		int n, s; scanf("%d%d", &n, &s);
		for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
		memset(dp, 0, sizeof(dp));
		dp[0][0][0][0] = 1;
		for(int i = 1; i <= n; ++i){
			for(int j = 0; j <= s; ++j){
				for(int p = 0; p <= 2; ++p){
					for(int q = 0; q <= 2; ++q){
						//must yes
						if(j + a[i] <= s) (dp[j + a[i]][i][p + 1][q] += dp[j][i - 1][p][q]) %= mod;
						//must no
						(dp[j][i][p][q + 1] += dp[j][i - 1][p][q]) %= mod;
						//can yes
						if(j + a[i] <= s) (dp[j + a[i]][i][p][q] += dp[j][i - 1][p][q]) %= mod;
						//can no
						(dp[j][i][p][q] += dp[j][i - 1][p][q]) %= mod;
					}
				}
			}
		}
		int ans = 0;
		for(int i = 1; i <= s; ++i){
			(ans += dp[i][n][2][2]) %= mod;
		}
		ans = ans * 2ll % mod * 2ll % mod;
		printf("%d\n", ans);
	}
	return 0;
}