题目地址:http://poj.org/problem?id=3046

题目大意

大意是,给$T$种蚂蚁(编号1到$T$),每种蚂蚁$A_i$个,一共$A$个。求问蚂蚁组成的集合大小为$S$到$B$的个数(输出后六位即可)。

例如有这样的情况,{1, 1, 2, 2, 3},表示编号为1的蚂蚁2个,编号为2的蚂蚁2个,编号为3的蚂蚁1个。

他们能组成如下集合:

  1. 有3个集合大小为1个蚂蚁: {1} {2} {3}
  2. 有5个集合大小为2个蚂蚁: {1,1} {1,2} {1,3} {2,2} {2,3}
  3. 有5个集合大小为3个蚂蚁: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
  4. 有3个集合大小为4个蚂蚁: {1,2,2,3} {1,1,2,2} {1,1,2,3}
  5. 有1个集合大小为5个蚂蚁: {1,1,2,2,3}

思路

又是难炸的动态规划,这题是多重集的组合数。

先设$dp[i+1][j]$为前$i$种蚂蚁组成大小为$j$的集合个数,设$An[i]$表示第$i$种蚂蚁的个数。

为了从前$i$种蚂蚁取出$j$个,可以从前$i-1$种蚂蚁取出$j-k$个,在从第$i$种蚂蚁取出$k$个。

于是有

$$dp[i+1][j] = \sum_{k=0}^{min(j, An[i])} dp[i][j-k]$$

时间复杂度是$O(T m^2)$,$m$是一共取出$m$个。

来优化这个式子,

$$dp[i+1][j] = \sum_{k=0}^{min(j, An[i])} dp[i][j-k]$$

按讨论展开,

1.当$0 \leq j \leq An[i]$时,有

$$dp[i+1][j] = dp[i][j] + dp[i][j-1] + \cdots + dp[i][0]$$

2.当$j > An[i]$时,有

$$dp[i+1][j] = dp[i][j]+dp[i][j-1] + \cdots + dp[i][j-An[i]]$$

为了得出递推公式,由$j$前一项来,有

$$dp[i+1][j-1] = \sum_{k=0}^{min(j-1, An[i])} dp[i][j-1-k]$$

展开得

1.当$0 \leq (j-1) \leq An[i]$,有

$$dp[i+1][j-1] = dp[i][j-1]+dp[i][j-2]+\cdots+dp[i][0]$$

2.当$(j-1) > An[i]$时,有

$$dp[i+1][j-1] = dp[i][j-1]+dp[i][j-2]+\cdots+dp[i][j-An[i]]+dp[i][j-1-An[i]]$$

对比$dp[i+1][j]$的展开式,发现$dp[i+1][j-1]$在第一种情况和第二种情况都少了个$dp[i][j]$,在第二种情况多了项$dp[i][j-1-An[i]]$,即

$$dp[i+1][j] = \sum_{k=0}^{min(j, An[i])} dp[i][j-k] = \sum_{k=0}^{min(j-1, An[i])} dp[i][j-1-k]+dp[i][j]-dp[i][j-1-An[i]]$$

那么在$dp[i+1][j-1]$加上$dp[i][j]$,再减去$dp[i][j-1-An[i]]$(当$(j-1) < An[i]$时,减去0,也就是不减),即可递推得到$dp[i+1][j]$,即

$$dp[i+1][j] = dp[i+1][j-1]+dp[i][j]-dp[i][j-1-An[i]]$$

优化到$O(Tm)$。

AC代码

/*************************************************************************
    > File Name: 3046.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-02 五 20:10:48 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

const int MOD = 1000000;
int An[1005];
int T, A, S, B;
const int MAX_T = 1000 + 5;
const int MAX_M = 10000 + 5;
int dp[MAX_T][MAX_M]; // dp[i+1][j]从前i种物品中取出j个的组合总数


void solve() {
    for(int i=1; i<=T+1; ++i) dp[i][0] = 1; // 一个都不取的组合数为1
    for(int i=1; i<=T; ++i) {
        for(int j=1; j<=B; ++j) {
            if(j-1-An[i] >= 0)
                dp[i+1][j] = (dp[i+1][j-1] + dp[i][j] - dp[i][j-1-An[i]] + MOD) % MOD;
            else
                dp[i+1][j] = (dp[i+1][j-1] + dp[i][j]) % MOD;
        }
    }
    int ans = 0;
    for(int i=S; i<=B; ++i) ans = (ans + dp[T+1][i]) % MOD;
    cout << ans << endl;

}

int main()
{
#ifdef Oj
    freopen("3046.in", "r", stdin);
#endif
    cin >> T >> A >> S >> B;
    int n;
    for(int i=0; i<A; ++i) {
        cin >> n;
        ++An[n];
    }
    solve();
    return 0;
}