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：

 #include <cstdio>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int N = ;

 LL dp[][][]; //dp[i][j][k]表示包含i

 int a[N], b[N];

 void solve(int n, int m, int d) {

     memset(dp, , sizeof(dp));

     for(int i = ; i <= n; ++i) {

         dp[i][b[i]][] = ;

         for(int j = ; j < i; ++j) {

             for(int x = ; x < d; ++x) {

                 for(int y = ; y <= m; ++y) {

                     dp[i][(b[i] + x) % d][y] += dp[j][x][y - ];

                 }

             }

         }

     }

 }

 int main()

 {

     int t, n, q;

     scanf("%d", &t);

     for(int ca = ; ca <= t; ++ca) {

         scanf("%d %d", &n, &q);

         for(int i = ; i <= n; ++i) {

             scanf("%d", a + i);

         }

         printf("Case %d:\n", ca);

         while(q--) {

             int d, m;

             scanf("%d %d", &d, &m);

             for(int i = ; i <= n; ++i) {

                 b[i] = (a[i] % d + d) % d;

             }

             solve(n, m, d);

             LL ans = ;

             for(int i = ; i <= n; ++i) {

                 ans += dp[i][][m];

             }

             printf("%lld\n", ans);

         }

     }

     return ;

 }

优化后 0.012：

 #include <cstdio>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int N = ;

 LL dp[][][]; //dp[i][j][k]表示前i个

 int a[N], b[N];

 void solve(int n, int m, int d) {

     memset(dp, , sizeof(dp));

     for(int i = ; i <= n; ++i) {

         dp[i][b[i]][] = ;

         for(int j = ; j < d; ++j) {

             for(int x = ; x <= m; ++x) {

                 dp[i][(b[i] + j) % d][x] += dp[i - ][j][x - ];

                 dp[i][j][x] += dp[i - ][j][x];

             }

         }

     }

 }

 int main()

 {

     int t, n, q;

     scanf("%d", &t);

     for(int ca = ; ca <= t; ++ca) {

         scanf("%d %d", &n, &q);

         for(int i = ; i <= n; ++i) {

             scanf("%d", a + i);

         }

         printf("Case %d:\n", ca);

         while(q--) {

             int d, m;

             scanf("%d %d", &d, &m);

             for(int i = ; i <= n; ++i) {

                 b[i] = (a[i] % d + d) % d;

             }

             solve(n, m, d);

             printf("%lld\n", dp[n][][m]);

         }

     }

     return ;

 }