UVa 10616 Divisible Group Sums：DFS以及DP

UVa 10616 Divisible Group Sums：DFS以及DP2014-07-07 synapse7

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=014.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:
", ++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
", i, f（0, 0, 0））;31.}32.}33.return 0;34.}