poj 3046 Ant Counting dp 多重集组合数

缘起

日常水题 poj 3046 Ant Counting

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
A件物品分别隶属于T种（T的范围是[1,1000]）. 不同种类的物品可以互相区分，但是相同种类的物品无法区分. 从这些物品中取出m件有Xm种取法，其中1<=S<=m<=B<=A, 求出X_S+...+X_B. 每种物品的数量范围是[1,100]
例如A=5, 5件物品为{1,1,2,2,3}（即2件属于第一种,2件属于第二种,一件属于第三种）
取出1件物品的方式有3种——{1}，{2}，{3}，即X1=3
取出2件物品的方式有5种——{1,1} {1,2} {1,3} {2,2} {2,3} ,X2=5
取出3件物品的方式有5种: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3} ,X3=5
取出4件物品的方式有3种: {1,2,2,3} {1,1,2,2} {1,1,2,3} ,X4=3
取出5件物品的方式有1种: {1,1,2,2,3} ,X5=1
S=2,B=3的话, 则答案是X2+X3=5+5=10

【输入】
只有2行——第一行是T,A，S，B， 第二行是每件物品隶属于哪种物品.

【输出】
输出集合数量在[S,B]之间的集合数量之和

【样例输入】
3 5 2 3
1
2
2
1
3

【样例输出】
10

【限制】
Time limit 1000 ms
Memory limit 65536 kB

【来源】
USACO 2005 November Silver

令

1
dp[i][j]为前i种物品凑出j件物品的方法数.

假设第i种物品（标号为i）的物品数目为ai, 则按照第i种物品取多少件有如下dp公式
$$
dp[i][j]=\Sigma_{0\le k\le min(ai,j)} dp[i-1][j-k]
$$
答案是求dp[n][S,…,B]之和, 算法的规模是1000*1000*1000 （因为每种物品的数量在[1,100]范围内, 所以最多1000种物品咯~），dp很难接受.（一定会被T）

滚不滚动无所谓啦~

还有一个要考虑的是初始值. dp[0][0]=1 ，dp[0][j]=0 （j>0）, dp[i][0] = 1（i>=1）

先尝试记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#define MIN(a,b) ((a)>(b)?(b):(a))
//#define LOCAL

const int BASE = 1000000;
int dp[1005][1005],a[1005],t,A,s,b;

int sz(int i, int j)
{
	if (~dp[i][j])
	{
		return dp[i][j];
	}
	int ret = 0;
	for(int k = 0; k<=MIN(a[i], j); k++)
	{
		ret%=BASE;
		ret+=sz(i-1, j-k);
	}
	return ret%BASE;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	memset(dp, -1, sizeof(dp));
	scanf("%d%d%d%d", &t, &A,&s,&b);
	dp[0][0]=1;
	for (int j = 1;j<1005;j++)
	{
		dp[0][j] = 0;
	}
	for (int i = 1; i<1005;i++)
	{
		dp[i][0] = 1;
	}
	for (int i = 0,x;i<A;i++)
	{
		scanf("%d", &x);
		a[x]++;
	}
	int ans = 0;
	for (int j = s; j<=b;j++)
	{
		ans%=BASE;
		ans+=sz(t,j);
	}
	ans%=BASE;
	printf("%d\n",ans);
	return 0;
}

被T掉了（我发现记忆化搜索其实非常耗时~）. 所以只能尝试dp. 但是dp的式子是O(N^3)的诶~

但是我们要发挥中学数学学数列学过的——作差法.
$$
dp[i][j]=\Sigma_{0\le k\le min(ai,j)} dp[i-1][j-k]
$$

$$
dp[i][j-1]=\Sigma_{0\le k\le min(ai,j-1)} dp[i-1][j-1-k]
$$
则两式做差得到（）
$$
\begin{align}
dp[i][j]-dp[i][j-1]=&dp[i-1][j]+dp[i-1][j-1]+…+dp[i-1][j-min(ai,j)]-\
&(dp[i-1][j-1]+dp[i-1][j-2]+…+dp[i-1][j-1-min(ai,j-1)]) \
=& dp[i-1][j]-dp[i-1][j-1-min(ai,j)]-…-dp[i-1][j-1-min(ai,j-1)]
\end{align}
$$
于是
$$
dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-min(ai,j)]-…-dp[i-1][j-1-min(ai,j-1)]
$$
如果ai<=j-1, 则上式等于
$$
dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a_i]
$$
如果ai>=j, 则（）式第一个等号等价于
$$
dp[i][j]=dp[i][j-1]+dp[i-1][j]
$$
总之，我们有dp公式如下.
$$
dp[i][j]=
\begin{cases}
dp[i][j-1]+dp[i-1][j], \ if \ j\le a_i \
dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a_i], \ if \ j \gt a_i
\end{cases}
$$

是不是有点神奇? 巧妙的通过作差法将O(n^3)复杂度转换为O(N^2). 高中数学就是这么做的!!!

初始值显然不用变动的. 再来看dp遍历的顺序. i从1到n作为外层循环, j从1到n作为内层循环.即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

const int BASE = 1e6;
int dp[1005][10005],a[1005],t,A,s,b;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d%d%d", &t, &A,&s,&b);
	for (int i = 0; i<=t;i++)
	{
		dp[i][0] = 1;
	}
	for (int i = 0,x;i<A;i++)
	{
		scanf("%d", &x);
		a[x]++;
	}
	for (int i = 1; i<=t;i++)
	{
		for (int j = 1; j<=A; j++)
		{
			if (j>a[i])
			{
				dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i]]+BASE)%BASE; // 注意, 这里不能写成dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i]])%BASE 因为不能保证非负（WA了几发）,所以这是一种保险的写法
			}
			else
			{
				dp[i][j] = (dp[i][j-1]+dp[i-1][j]+BASE)%BASE;
			}
		}
	}
	int ans = 0;
	for (int j = s; j<=b;j++)
	{
		ans%=BASE;
		ans+=dp[t][j];
	}
	ans%=BASE;
	printf("%d\n",ans);
	return 0;
}

ac情况

Status Accepted
Time 79ms
Memory 3812kB
Length 841
Lang C++
Submitted 2019-08-20 15:10:01
Shared
RemoteRunId 20773806