MYF

HDU 5800 To My Girlfriend

Posted on | In | | Visitors

题目链接

HDU 5800

题目类型：动态规划

题目来源：2016 Multi-University Training Contest 6

题目分析

题目大意

给出$n$个数字，问存在多少组组合，使组合必然有某两个数字，必然没有指定两个数，且组合内的数之和为$m$

解析

看了题解之后，发现还有这么神奇的设置状态的方法。

$dp[i][j][x][y]$表示的是，对于第$i$个数的情况，该情况内的所有数之和为$j$，有$x$个数字必然取，有$y$个数字必然不取。这样对于当前的数字，有四种状态，必选当前数字，必然不选当前数字，可以选当前数字，可以不选当前数字，然后确定好边界进行状态转移即可。

分析一下为什么要设置这样的DP数组，首先要枚举所有数，所以有第一维长度为$n$的数组，第二维控制数之和（有的情况下也可以当成花费之类的），第三维表示当前必然选择了的数字个数，第四维表示当前必然不选的数字的个数。对于类似的题，可以通过不同的维数来把握要控制的条件数量，每一维的长度为当前条件的情况数量。把握好这一段的内容，想到这个状态转移其实并不是很难的还是。此外，要值得注意的是DP临界情况的确定

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int dp[1005][1005][3][3];
int a[1005];
void add(int &x,int y){
    x = ( x + y ) % mod;
}
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        int n ,m;
        scanf("%d%d",&n,&m);
        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<=m; j++) {
                for (int x = 0; x<3; x++) {
                    for (int y=0; y<3; y++) {
                        
                        // 选
                        if (j>=a[i])
                            add(dp[i][j][x][y], dp[i-1][j-a[i]][x][y]);
                        
                        // 不选
                        add(dp[i][j][x][y], dp[i-1][j][x][y]);
                        
                        // 必选
                        if (x>=1&&j>=a[i])
                            add(dp[i][j][x][y], dp[i-1][j-a[i]][x-1][y]);
                        
                        // 必不选
                        if (y>=1)
                            add(dp[i][j][x][y], dp[i-1][j][x][y-1]);

                    }
                }
            }
        }
        ll ans = 0;
        for (int i=0; i<=m; i++)
            ans += dp[n][i][2][2];
        cout<<ans*4%mod<<endl;
    }
}