挑战练习题2.3动态规划 poj3046 Ant Counting dp

题目链接:

http://poj.org/problem?id=3046

题意:

有T种蚂蚁，共A只。同一个种的蚂蚁长得一样，但是不同种的蚂蚁牙齿颜色不同。任取n只蚂蚁(S<=n<=B)，求能组成几种集合？

题解:

dp[i][j] := 使用前i个种可以配出来j个的集合的个数。
那么dp[0][0] = 1，不使用任何蚂蚁配出空集的个数为1。

挑战P69页的优化(O(n^2))真TM不懂

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;
const int mod = 1e6;

int dp[1000][maxn];
int a[maxn];

int main(){
    int T,A,S,B;
    cin >> T >> A >> S >> B;
    for(int i=1; i<=A; i++){
        int x; cin >> x;
        ++a[x];
    }

    // dp[i][j] = dp[i-1][j]+dp[i][j-k]; 使用前i个家族可以配出来“元素个数为j”的集合的个数

    dp[0][0] = 1;
    int tot = 0;
    for(int i=1; i<=T; i++){
        tot += a[i];
        for(int j=0; j<=tot; j++){
            for(int k=0; k<=a[i] && j>=k; k++){
                dp[i][j] = (dp[i][j]+dp[i-1][j-k])%mod;
            }
        }
    }

    ll ans = 0;
    for(int i=S; i<=B; i++)
        ans = (ans + dp[T][i])%mod;

    cout << ans << endl;

    return 0;
}

滚动优化

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 #define MS(a) memset(a,0,sizeof(a))
 7 #define MP make_pair
 8 #define PB push_back
 9 const int INF = 0x3f3f3f3f;
10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
11 inline ll read(){
12     ll x=0,f=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 //////////////////////////////////////////////////////////////////////////
18 const int maxn = 1e5+10;
19 const int mod = 1e6;
20 
21 int dp[2][maxn];
22 int a[maxn];
23 
24 int main(){
25     int T,A,S,B;
26     cin >> T >> A >> S >> B;
27     for(int i=1; i<=A; i++){
28         int x; cin >> x;
29         ++a[x];
30     }
31 
32     // dp[i][j] = dp[i-1][j]+dp[i][j-k]; 使用前i个家族可以配出来“元素个数为j”的集合的个数
33 
34     int now=0,pre=1;
35     dp[now][0] = 1;
36     int tot = 0;
37     for(int i=1; i<=T; i++){
38         tot += a[i];
39         swap(now,pre);
40         MS(dp[now]);
41         for(int j=0; j<=tot; j++){
42             for(int k=0; k<=a[i] && j>=k; k++){
43                 dp[now][j] = (dp[now][j]+dp[pre][j-k])%mod;
44             }
45         }
46     }
47 
48     ll ans = 0;
49     for(int i=S; i<=B; i++)
50         ans = (ans + dp[now][i])%mod;
51 
52     cout << ans << endl;
53 
54     return 0;
55 }

蜜汁优化：我写了啥？

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 #define MS(a) memset(a,0,sizeof(a))
 7 #define MP make_pair
 8 #define PB push_back
 9 const int INF = 0x3f3f3f3f;
10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
11 inline ll read(){
12     ll x=0,f=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 //////////////////////////////////////////////////////////////////////////
18 const int maxn = 1e5+10;
19 const int mod = 1e6;
20 
21 int dp[1005][maxn];
22 int a[maxn];
23 
24 int main(){
25     int T,A,S,B;
26     cin >> T >> A >> S >> B;
27     for(int i=1; i<=A; i++){
28         int x; cin >> x;
29         ++a[x];
30     }
31 
32     for(int i=0; i<=T; i++)
33         dp[i][0] = 1;
34 
35     for(int i=1; i<=T; i++){
36         for(int j=1; j<=A; j++){
37             if(j-1-a[i] >= 0)
38                 dp[i][j] = (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i]] + mod) % mod;
39             else
40                 dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % mod;
41         }
42     }
43 
44     ll ans = 0;
45     for(int i=S; i<=B; i++)
46         ans = (ans + dp[T][i]) % mod;
47     cout << ans << endl;
48 
49     return 0;
50 }