poj3046

dp,可以再优化。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int t,a,s,b,tmp;
 6 int x[1005];
 7 int dp[2][100005];
 8 const int mod = 1e6;
 9 void solve(int res)
10 {
11     for(int i = 0; i <= x[1]; i++)
12     {
13         dp[1][i] = 1;
14     }
15     for(int i = 2; i < t+1; i++)
16     {
17         memset(dp[i & 1], 0, sizeof(dp[i & 1]));
18         for(int j = 0; j <= res; j++)
19         {
20             for(int k = 0; k <= x[i] && k <= j; k++)
21             {
22                 dp[i & 1][j] = (dp[i & 1][j] + dp[(i-1) & 1][j-k]) % mod;
23             }
24         }
25     }
26 }
27 
28 int main()
29 {
30     cin >> t >> a >> s >> b;
31     for(int i = 0; i < a; i++)
32     {
33         scanf("%d", &tmp);
34         x[tmp]++;
35     }
36     int cnt = 0;
37     solve(a);
38     for(int i = s; i <= b; i++)
39     {
40         cnt = (cnt + dp[t & 1][i]) % mod;
41     }
42     cout << cnt << endl;
43     return 0;    
44 }