POJ 3046 Ant Counting——多重集组合数

POJ 3046 Ant Counting——多重集组合数

定义dp【i】【j】为从前i种物品中选j个物品对应的方案总数

状态转移方程为：dp【i】【j】 = ∑dp【i-1】【j-k】（k的范围是【0，min（j，cnt【i】）】）

优化的话只要写出dp【i】【j】和dp【i】【j-1】对应的求和展开式就能找到两者之间的关系，从而去掉一重循环

最后用滚动数组优化一下空间，虽然这题不优化也能过

#include #include #include #include using namespace std;const int mod = 1e6;int T, A, S, B, a[1005];int dp[2][100005];void solve() { dp[0][0] = dp[1][0] = 1; for (int i = 1; i <= T; i++) { for (int j = 1; j <= B; j++) { if (j - 1 >= a[i]) dp[i&1][j] = (dp[i&1][j-1]+dp[(i-1)&1][j]-dp[(i-1)&1][j-1-a[i]]+mod)%mod; else dp[i&1][j] = (dp[i&1][j-1]+dp[(i-1)&1][j])%mod; } }}int main() { while (~scanf("%d %d %d %d", &T, &A, &S, &B)) { memset(a, 0, sizeof(a)); int x; for (int i = 1; i <= A; i++) { scanf("%d", &x); a[x]++; } solve(); int ans = 0; for (int i = S; i <= B; i++) ans = (ans + dp[T&1][i])%mod; printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。