hdu 5800 To My Girlfriend + dp

题意：给定n个物品，其中i,j必选，l,m必不选，问组成体积为s的方法一共有多少种

思路：定义dp[i][j][s1][s2],表示前i种物品能够构成的体积为j，其中有s1种定为必选，s2种定为不必选;因为递推到第i层时，只与第i-1层有关，所以把第一维降到2来省内存。然后就是dp[i][j][s1][s2]=dp[i-1][j][s1][s2]+dp[i-1][j][s1][s2-1]+dp[i-1][j-a[i]][s1-1][s2]+dp[i-1][j-a[i]][s1][s2];然后就是对i,j,l,m排序了，A(2,2)*A(2，2)

/**************************************************************

    Problem:hdu 5800 To My Girlfriend

    User: youmi

    Language: C++

    Result: Accepted

    Time:1903MS

    Memory:1716K

****************************************************************/

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#include <cmath>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#define zeros(a) memset(a,0,sizeof(a))

#define ones(a) memset(a,-1,sizeof(a))

#define sc(a) scanf("%d",&a)

#define sc2(a,b) scanf("%d%d",&a,&b)

#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define scs(a) scanf("%s",a)

#define sclld(a) scanf("%I64d",&a)

#define pt(a) printf("%d\n",a)

#define ptlld(a) printf("%I64d\n",a)

#define rep(i,from,to) for(int i=from;i<=to;i++)

#define irep(i,to,from) for(int i=to;i>=from;i--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define lson (step<<1)

#define rson (lson+1)

#define eps 1e-6

#define oo 0x3fffffff

#define TEST cout<<"*************************"<<endl

const double pi=*atan(1.0);

using namespace std;

typedef long long ll;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

int Pow(int base, ll n, int mo)

{

    if (n == ) return ;

    if (n == ) return base % mo;

    int tmp = Pow(base, n >> , mo);

    tmp = (ll)tmp * tmp % mo;

    if (n & ) tmp = (ll)tmp * base % mo;

    return tmp;

}

//***************************

int n,s;

const int maxn=+;

const ll mod=;

ll dp[][maxn][][];

int a[maxn];

ll ans;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    int T_T;

    scanf("%d",&T_T);

    for(int kase=;kase<=T_T;kase++)

    {

        sc2(n,s);

        rep(i,,n)

            sc(a[i]);

        zeros(dp);

        ll ans=;

        dp[][][][]=;

        int temp=;

        rep(i,,n)

        {

            zeros(dp[temp]);

            rep(j,,s)

                rep(s1,,)

                    rep(s2,,)

                    {

                        dp[temp&][j][s1][s2]=(dp[temp&][j][s1][s2]+dp[temp^][j][s1][s2])%mod;

                        if(s2>=)

                            dp[temp&][j][s1][s2]=(dp[temp&][j][s1][s2]+dp[temp^][j][s1][s2-])%mod;

                        if(s1>=&&j>=a[i])

                            dp[temp&][j][s1][s2]=(dp[temp&][j][s1][s2]+dp[temp^][j-a[i]][s1-][s2])%mod;

                        if(j>=a[i])

                            dp[temp&][j][s1][s2]=(dp[temp&][j][s1][s2]+dp[temp^][j-a[i]][s1][s2])%mod;

                    }

            temp^=;

        }

        temp^=;

        rep(j,,s)

                ans=(ans+dp[temp][j][][])%mod;

        ans=(ans*)%mod;

        ptlld(ans);

    }

}

秒客网

hdu 5800 To My Girlfriend + dp

相关文章