數位DP三題 hdu2089 hdu3652 hdu4734

acm dp

學習數位DP所做的三題

hdu2089

hdu2089.cpp
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
#include <cstdio>
#include <cstring>

typedef long long LL;

LL num[15];

LL dodfs(int len, bool preSix, bool limitR) {
  if(len == 0) return 1;
  LL result = 0;
  int limit = limitR?num[len]:9;
  for(int i = 0; i <= limit; ++i) {
    if(preSix && i == 2 || i == 4) continue;
    result += dodfs(len-1, i == 6, limitR&&i==limit);
  }
  return result;
}

int count_digit(LL n) {
  memset(num, 0, sizeof(num));
  int len = 1;
  while(n > 0) {
    num[len++] = n % 10;
    n /= 10;
  }
  return len - 1;
}

LL solve(LL n) {
  if(n == -1) return 0;
  int count = count_digit(n);
  return dodfs(count, false, true);
}

int main() {
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  LL start, end;
  while(scanf("%lld%lld", &start, &end) != EOF && (start || end)) {
    printf("%lld\n", solve(end) - solve(start-1));
  }
  return 0;
}

hdu3652

hdu3652.cpp
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
#include <cstdio>
#include <cstring>

typedef long long LL;

// len | have 13 | preNum | mod
LL dp[15][2][10][13];
LL num[15];

LL dodp(int len, int preMod, int preNum, bool have13, bool limitR) {
  if(len == 0) return have13 && preMod == 0;
  int type = 0;

  if(!limitR && dp[len][have13][preNum][preMod] != -1)
    return dp[len][have13][preNum][preMod];

  int limit = limitR?num[len]:9;
  LL ans = 0;
  for(int i = 0; i <= limit; ++i) {
    ans += dodp(len-1, (((preMod*10)%13)+i)%13, i, have13||(preNum==1&&i==3), limitR&&i==limit);
  }
  if(!limitR) {
    dp[len][have13][preNum][preMod] = ans;
  }
  return ans;
}

int count_digit(LL n) {
  memset(num, 0, sizeof(num));
  int len = 1;
  while(n > 0) {
    num[len++] = n % 10;
    n /= 10;
  }
  return len - 1;
}


int main() {
  // freopen("input.txt", "r", stdin);
  memset(dp, -1, sizeof(dp));

  LL n;
  while(scanf("%lld", &n) != EOF) {
    int len = count_digit(n);
    printf("%lld\n", dodp(len, 0, 0, false, true));
  }
  return 0;
}

hdu4734

hdu4734.cpp
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>

int dp[10][2000];
int num[10];
int w;
int accum;

int ten[10];


int dodp(int len, int cw, int an, bool limitR) {
  if(len == 0) return cw <= w;
  if(cw > w) return 0;
  if(!limitR && dp[len][cw] != -1)
    return dp[len][cw];

  int limit = limitR?num[len]:9;
  int ans = 0;
  int next_an = an>>1;
  for(int i = 0; i <= limit; ++i) {
    int tmp = cw + i*an;
    if(tmp > w) continue;
    if(!limitR && tmp+9*(an-1)<= w) {
      // max weight when n = 1, 2, 3, 4, 5  = 9 ,27, 63, 135
      //                   = 9 * (2^0 + 2^1 + ... 2^n)
      //                   = 9 * (2^(n+1) - 1)
      ans += ten[len - 1];
    } else if (tmp == w) {
      ans++;
    } else {
      ans += dodp(len-1, tmp, next_an, limitR&&i==limit);
    }
  }

  if(!limitR) dp[len][cw] = ans;

  return ans;
}

void calc_weight(int n) {
  int ac = 1;
  w = 0;
  while(n > 0) {
    w += ac * (n % 10);
    n /= 10;
    ac <<= 1;
  }
}

int solve(int n) {
  int len = 1;
  accum = 1;
  while(n > 0) {
    num[len++] = n % 10;
    n /= 10;
    accum <<= 1;
  }
  accum >>= 1;
  len--;
  // printf("len: [%d]  accum: [%intd]  w: [%intd]\n", len, accum, w);
  return dodp(len, 0, accum, true);
}

int main() {
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  int T;
  int a, b;
  // clock_t begin_time = clock();
  ten[0] = 1;
  for(int i = 1; i < 10; ++i) ten[i] = ten[i-1]*10;
  scanf("%d", &T);
  for(int tc = 1; tc <= T; ++tc) {
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &a, &b);
    calc_weight(a);
    printf("Case #%d: %d\n", tc, solve(b));
  }
  // printf("%lf\n", float( clock () - begin_time ));
}