首页 > 代码库 > Light oj 1125 - Divisible Group Sums (dp)
Light oj 1125 - Divisible Group Sums (dp)
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1125
题意：
给你n个数，q次询问，每次询问问你取其中m个数是d的整数倍的方案数。
题意：
dp[i][j][k] 表示前i个数, %d=j, 取了k个的方案数。
| ID | SUBMISSION TIME | PROBLEM | SOURCE | CPU | MEMORY | VERDICT |
|---|---|---|---|---|---|---|
| 839200 | 2016-10-15 14:59:00 | 1125 - Divisible Group Sums | C++ | 0.012 | 1688 | Accepted |
| 839186 | 2016-10-15 14:35:08 | 1125 - Divisible Group Sums | C++ | 0.336 | 1688 | Accepted |
没优化前 0.336：
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 typedef long long LL; 5 const int N = 205; 6 LL dp[205][25][15]; //dp[i][j][k]表示包含i 7 int a[N], b[N]; 8 9 void solve(int n, int m, int d) {10 memset(dp, 0, sizeof(dp));11 for(int i = 1; i <= n; ++i) {12 dp[i][b[i]][1] = 1;13 for(int j = 1; j < i; ++j) {14 for(int x = 0; x < d; ++x) {15 for(int y = 2; y <= m; ++y) {16 dp[i][(b[i] + x) % d][y] += dp[j][x][y - 1];17 }18 }19 }20 }21 }22 23 int main()24 {25 int t, n, q;26 scanf("%d", &t);27 for(int ca = 1; ca <= t; ++ca) {28 scanf("%d %d", &n, &q);29 for(int i = 1; i <= n; ++i) {30 scanf("%d", a + i);31 }32 printf("Case %d:\n", ca);33 while(q--) {34 int d, m;35 scanf("%d %d", &d, &m);36 for(int i = 1; i <= n; ++i) {37 b[i] = (a[i] % d + d) % d;38 }39 solve(n, m, d);40 LL ans = 0;41 for(int i = 1; i <= n; ++i) {42 ans += dp[i][0][m];43 }44 printf("%lld\n", ans);45 }46 }47 return 0;48 }
优化后 0.012：
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 typedef long long LL; 5 const int N = 205; 6 LL dp[205][25][15]; //dp[i][j][k]表示前i个 7 int a[N], b[N]; 8 9 void solve(int n, int m, int d) {10 memset(dp, 0, sizeof(dp));11 for(int i = 1; i <= n; ++i) {12 dp[i][b[i]][1] = 1;13 for(int j = 0; j < d; ++j) {14 for(int x = 1; x <= m; ++x) {15 dp[i][(b[i] + j) % d][x] += dp[i - 1][j][x - 1];16 dp[i][j][x] += dp[i - 1][j][x];17 }18 }19 }20 }21 22 int main()23 {24 int t, n, q;25 scanf("%d", &t);26 for(int ca = 1; ca <= t; ++ca) {27 scanf("%d %d", &n, &q);28 for(int i = 1; i <= n; ++i) {29 scanf("%d", a + i);30 }31 printf("Case %d:\n", ca);32 while(q--) {33 int d, m;34 scanf("%d %d", &d, &m);35 for(int i = 1; i <= n; ++i) {36 b[i] = (a[i] % d + d) % d;37 }38 solve(n, m, d);39 printf("%lld\n", dp[n][0][m]);40 }41 }42 return 0;43 }
Light oj 1125 - Divisible Group Sums (dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。