题目链接：

题意：

给你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
      
        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\n",(ans<<2)%P);30     }31     return 0;32 }