挑战练习题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; }

滚动优化

#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[2][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”的集合的个数 int now=0,pre=1; dp[now][0] = 1; int tot = 0; for(int i=1; i<=T; i++){ tot += a[i]; swap(now,pre); MS(dp[now]); for(int j=0; j<=tot; j++){ for(int k=0; k<=a[i] && j>=k; k++){ dp[now][j] = (dp[now][j]+dp[pre][j-k])%mod; } } } ll ans = 0; for(int i=S; i<=B; i++) ans = (ans + dp[now][i])%mod; cout << ans << endl; return 0; }

蜜汁优化： 我写了啥？

#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[1005][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]; } for(int i=0; i<=T; i++) dp[i][0] = 1; for(int i=1; i<=T; i++){ for(int j=1; j<=A; j++){ if(j-1-a[i] >= 0) dp[i][j] = (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i]] + mod) % mod; else dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % mod; } } ll ans = 0; for(int i=S; i<=B; i++) ans = (ans + dp[T][i]) % mod; cout << ans << endl; return 0; }