UVa 10616 Divisible Group Sums：DFS以及DP

10616 - Divisible Group Sums

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1557

思路：用DFS+记忆化搜索枚举组合，注意数字有<0的。

return dp[i][cnt][sum] = f(i + 1, cnt + 1, ((sum + arr[i]) % d + d) % d) + f(i + 1, cnt, sum);///i<n,cnt<m

完整代码：

01./*0.055s*/
02.
03.#include<cstdio>
04.#include<cstring>
05.typedef long long ll;
06.
07.ll dp[205][15][25];
08.int d, m, n, arr[205];
09.
10.ll f(int i, int cnt, ll sum)
11.{
12.    if (cnt == m) return dp[i][cnt][sum] = (sum % d ? 0 : 1);///选m个
13.    if (i == n) return dp[i][cnt][sum] = 0;///总共n个，如果i==n，说明cnt!=m，也就是还没有选完，此时dp=0
14.    if (dp[i][cnt][sum] >= 0) return dp[i][cnt][sum];
15.    return dp[i][cnt][sum] = f(i + 1, cnt + 1, ((sum + arr[i]) % d + d) % d) + f(i + 1, cnt, sum);
16.}
17.
18.int main()
19.{
20.    int cas = 0, q, i, ans;
21.    while (scanf("%d%d", &n, &q), n)
22.    {
23.        for (i = 0; i < n; ++i) scanf("%d", &arr[i]);
24.        printf("SET %d:\n", ++cas);
25.        for (i = 1; i <= q; ++i)
26.        {
27.            ans = 0;
28.            memset(dp, -1, sizeof(dp));
29.            scanf("%d%d", &d, &m);
30.            printf("QUERY %d: %d\n", i, f(0, 0, 0));
31.        }
32.    }
33.    return 0;
34.}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索dfs
， 思路
， category
group
group by、ikongroup、恒地金融hengdigroup、group、蓝骄lanjiaogroup，以便于您获取更多的相关知识。