poj-3046 Ant Counting【dp】【母函数】

题目链接：戳这里

题意：有A只蚂蚁，来自T个家族，每个家族有ti只蚂蚁。任取n只蚂蚁(S <= n <= B)，求能组成几种集合？

这道题可以用dp或母函数求。

多重集组合数也是由多重背包问题拓展出来的一类经典问题,而此类问题也都可以用母函数求.

给大家讲2种方法：

①朴素方法：

状态：dp[i][j]：前i种中选j个可以组成的集合数

决策：第i种选k个，k<=cnt[i] && j-k>=0

转移：dp[i][j]=Σdp[i-1][j-k]

复杂度为O（B*Σant[i]）即O（B*A）也即O（A^2），虽说这题A最大可到1e5，但是实际数据水，能过

其实这个所谓的朴素dp算法就是母函数的算法.

附ac代码：

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 using namespace std;

 5 typedef unsigned long long ll;

 6 const int maxn = 1e3 + 10;

 7 const int inf = 0x3f3f3f3f;

 8 const int maxx = 1e5 + 10;

 9 int dp[2][maxx];

10 int cnt[maxn];

11 int num[maxn];

12 const int mod = 1e6;

13 int main()

14 {

15     int t, a, s ,b, u;

16     scanf("%d %d %d %d", &t, &a, &s, &b);

17     for(int i = 1; i <= a; ++i)

18     {

19         scanf("%d", &u);

20         ++cnt[u];

21     }

22     //处理边界问题，当只有一种蚂蚁的时候，无论多少个蚂蚁，组成的集合都是1

23     for(int i = 0; i <= cnt[1]; ++i) // 这里从0开始赋值是为了后面当j- k = 0时dp[][j-k]=1

24     dp[1][i] = 1;

25     for(int i = 2; i <= t; ++i)

26     {//这里j=0依然是处理边界，比如dp[3][1] = dp[2][0] + dp[2][1]

27         for(int j = 0; j <= b; ++j)

28         {

29             for(int k = 0; k <= min(j, cnt[i]); ++k)

30             {

31                 dp[i & 1][j] = (dp[i & 1][j] + dp[(i & 1) ^ 1][j - k]) % mod;

32

33             }

34        //     printf("%d %d %d\n", dp[i&1][j], i, j);

35         }

36         memset(dp[(i & 1) ^ 1], 0, sizeof(dp[(i & 1) ^ 1]));

37     }

38     int ans = 0;

39     for(int i = s; i <= b; ++i)

40     {

41         ans = (ans + dp[t & 1][i]) % mod;

42     }

43     printf("%d\n", ans);

44     return 0;

45 }

②优化递推式

状态：dp[i][j]：前i种中选j个可以组成的集合数

决策：第i种不选或者至少选一个

转移： dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-cnt[i]-1] (j-cnt[i]-1>=0)

优化思路：

根据①可以知道

dp[i][j]=∑{k=0~min(j,cnt[i])} dp[i][j-k]

所以dp[i][j-1]=∑(k=0~min(j-1,cnt[i])} dp[i][j-1-k]

二者之间的关系是:

dp[i][j]=dp[i][j-1]+dp[i][j-1]-dp[i-1][j-cnt[i]-1] 即得出优化的转移方程.

通俗来说,就是从前i种中取j个只与从前i种中取j-1个有两种情况不同,其他都是一样的.

这样就省去了大量的重复运算.

复杂度为O（T*B）

附ac代码:

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 using namespace std;

 5 typedef unsigned long long ll;

 6 const int maxn = 1e3 + 10;

 7 const int inf = 0x3f3f3f3f;

 8 const int maxx = 1e5 + 10;

 9 int dp[2][maxx];

10 int cnt[maxn];

11 int num[maxn];

12 const int mod = 1e6;

13 int main()

14 {

15     int t, a, s ,b, u;

16     scanf("%d %d %d %d", &t, &a, &s, &b);

17     for(int i = 1; i <= a; ++i)

18     {

19         scanf("%d", &u);

20         ++cnt[u];

21     }

22     //处理边界问题，当只有一种蚂蚁的时候，无论多少个蚂蚁，组成的集合都是1

23     for(int i = 0; i <= cnt[1]; ++i) // 这里从0开始赋值是为了后面当j- k = 0时dp[][j-k]=1

24     dp[1][i] = 1;

25     for(int i = 2; i <= t; ++i)

26     {//这里j=0依然是处理边界，比如dp[3][1] = dp[2][0] + dp[2][1]

27         for(int j = 0; j <= b; ++j)

28         {

29                 dp[i & 1][j] = (dp[i & 1][j] + dp[(i & 1) ^ 1][j] + dp[i & 1][j - 1])%mod;

30                 if(j - 1 - cnt[i] >= 0)

31                     dp[i & 1][j] = (dp[i & 1][j] - dp[(i & 1) ^ 1][j - 1 - cnt[i]] + mod)%mod;//+mod防止负数

32        //     printf("%d %d %d\n", dp[i&1][j], i, j);

33         }

34         memset(dp[(i & 1) ^ 1], 0, sizeof(dp[(i & 1) ^ 1]));

35     }

36     int ans = 0;

37     for(int i = s; i <= b; ++i)

38     {

39         ans = (ans + dp[t & 1][i])%mod;

40     }

41     printf("%d\n", ans);

42     return 0;

43 }

参考博客:戳这里

巴特西

poj-3046 Ant Counting【dp】【母函数】

最新文章

热门文章