总结
1. 编程之美讲了剪枝解法, 这里给出动规解法
2. dp[i][j]%n = j. dp[i][j] 是 mod n 余 j 的最小值
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 |
/* * source.cpp * * Created on: Apr 6, 2014 * Author: sangs */#include <stdio.h>#include <iostream>#include <string>#include <vector>#include <memory.h>using
namespace std;typedef
unsigned long
long LL;LL dp[200][500];LL cal(int
n) { LL lastModed = 1; LL expr10 = 1; memset(dp, 0, sizeof(dp)); dp[0][1] = 1; for(int
i = 1; ; i ++) { for(int
j = 1; j < n; j ++) { dp[i][j] = dp[i-1][j]; } LL thisModed = (lastModed*(10%n))%n; lastModed = thisModed; expr10 *= 10; if(dp[i-1][thisModed] == 0) { dp[i][thisModed] = expr10; } //cout << dp[i][thisModed] << endl; for(int
j = 1; j < n; j ++) { if(dp[i-1][j] == 0) { continue; } LL candy = (j + thisModed)%n; if(dp[i][candy] == 0) { dp[i][candy] = expr10 + dp[i-1][j]; } } if(dp[i][0] != 0) { return
dp[i][0]; } } return
1;}int
main() { freopen("input.txt", "r", stdin); int
n; while(scanf("%d", &n) != EOF && n != 0) { LL res = cal(n); printf("%lld\n", res); } return
0;} |
POJ 1426 Find the Multiple(二维DP),布布扣,bubuko.com
POJ 1426 Find the Multiple(二维DP)
原文：http://www.cnblogs.com/zhouzhuo/p/3649208.html