HDU5800 To My Girlfriend 背包计数dp

分析：首先定义状态dp[i][j][s1][s2]代表前i个物品中，选若干个物品，总价值为j

其中s1个物品时必选，s2物品必不选的方案数

那么转移的时候可以考虑，第i个物品是可选可可不选的

dp[i][j][s1][s2]+=dp[i-1][j][s1][s2]+dp[i-1][j-a[i]][s1][s2]

或者第i个物品必选，或者必不选

dp[i][j][s1][s2]+=dp[i-1][j-a[i]][s1-1][s2]+dp[i-1][j][s1][s2-1]

一点感想：这个题边界时dp[0][0][0][0]=1；

当i不等于0时，dp[i][0][s1][s2]也是有意义的，因为可以代表s2个物品必不选，所以从0开始

由于空间是O(9E6)的，太大，类似01背包优化成一维O(9e3)

时间复杂度O(N*S*9)(发现又是一道计数dp，一般涉及计数的dp不是特别好做，主要是人傻)

#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e3+1;
const int mod = 1e9+7;
int dp[N][3][3];
int a[N],T,n,s;
inline void up(int &x,int y){
  x+=y;if(x>=mod)x-=mod;
}
inline int mul(int x,int y){
  int ret=(1ll*x*y)%(1ll*mod);
  return ret;
}
int main(){
  scanf("%d",&T);
  while(T--){
    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]=1;
    for(int i=1;i<=n;++i)
     for(int j=s;j>=0;--j)
      for(int s1=2;s1>=0;--s1)
       for(int s2=2;s2>=0;--s2){
          int tmp=0;
          up(tmp,dp[j][s1][s2]);
          if(j>=a[i])up(tmp,dp[j-a[i]][s1][s2]);
          if(s1&&j>=a[i])up(tmp,dp[j-a[i]][s1-1][s2]);
          if(s2)up(tmp,dp[j][s1][s2-1]);
          dp[j][s1][s2]=tmp;
       }
    int ret=0;
    for(int i=1;i<=s;++i)up(ret,dp[i][2][2]);
    ret=mul(ret,4);
    printf("%d
",ret);   
  }
  return 0;
}

View Code