hdu_5800_To My Girlfriend(变种背包)

题意：

给你n和物品和一个重量m，让你求

题解：

To My Girlfriend

令dp[i][j][s1][s2]表示前i个物品填了j的体积，有s1个物品选为为必选，s2个物品选为必不选的方案数(0<=s1,s2<=2)，则有转移方程dp[i][j][s1][s2] = dp[i - 1][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，时间复杂度O(NS*3^2)。

由于顺序可以交换，最后结果要*4

 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int N=1011,P=1e9+7;
 8 int t,n,s,a[N],dp[N][N][3][3];
 9 
10 inline void add(int &a,int b){a+=b;if(a>P)a-=P;}
11 
12 int main(){
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%d%d",&n,&s);
17         F(i,1,n)scanf("%d",a+i);
18         mst(dp,0),dp[0][0][0][0]=1;
19         F(i,1,n)F(j,0,s)F(ii,0,2)F(jj,0,2)
20         {
21             int *p=&dp[i][j][ii][jj];
22             add(*p,dp[i-1][j][ii][jj]);//不塞
23             if(j>=a[i])add(*p,dp[i-1][j-a[i]][ii][jj]);//塞
24             if(ii>0&&j>=a[i])add(*p,dp[i-1][j-a[i]][ii-1][jj]);//放入必塞
25             if(jj>0)add(*p,dp[i-1][j][ii][jj-1]);//放入必不塞
26         }
27         ll ans=0;
28         F(i,1,s)ans=(ans+dp[n][i][2][2])%P;
29         printf("%d
",(ans<<2)%P);
30     }
31     return 0;
32 }

View Code