HDU 5800 （DP）

Problem To My Girlfriend （HDU 5800）

题目大意

　　给定一个由n个元素组成的序列,和s (n<=1000,s<=1000)

　　求：

　　f (i，j，k，l，m) 指必定选第i，j号元素，必定不选k，l号元素，选的元素总和为m的子集个数。

解题分析

　　一开始想了个n^3的DP，f[j][k]表示选j个数总和为k的方案数，然后一直想着怎么去优化，陷进死胡同，到比赛结束还没想出来。

　　看了题解后，感觉智商被藐视了。

　　题解的做法是f[i][j][s1][s2]表示前i个数总和为j必选s1个必不选s2个的方案数，这样是O(n*s*9)的。

　　对于每一个数，有4种选法：选，不选，必选，必不选，然后转移就好了。

　　答案就是sigma(f[n][i][2][2]) ,i∈[0,s]。

参考程序

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 #define N 1008

 #define mo 1000000007

 int dp[N][N][][];

 int a[N];

 void add(int &x,int y){

     x = x + y;

     if (x >= mo) x -= mo;

 }

 int main(){

     int T;

     scanf("%d",&T);

     while (T--){

         int n,s;

         scanf("%d%d",&n,&s);

         for (int i=;i<=n;i++) scanf("%d",&a[i]);

         memset(dp,,sizeof(dp));

         dp[][][][]=;

         for (int i=;i<=n;i++)

             for (int j=;j<=s;j++)

                 for (int s1=;s1<=;s1++)

                     for (int s2=;s2<=;s2++){

                         add(dp[i][j][s1][s2],dp[i-][j][s1][s2]);

                         if (j>=a[i]) add(dp[i][j][s1][s2],dp[i-][j-a[i]][s1][s2]);

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

                             add(dp[i][j][s1][s2],dp[i-][j-a[i]][s1-][s2]);

                         if (s2>)

                             add(dp[i][j][s1][s2],dp[i-][j][s1][s2-]);

                     }

         int ans=;

         for (int i=;i<=s;i++) add(ans,dp[n][i][][]);

         printf("%I64d\n",ans*4ll % mo);

     }

 }

巴特西

HDU 5800 （DP）

最新文章

热门文章