求n到1的最小步数

发表于   |   分类于   |  

题目大意

　　http://www.spoj.com/problems/MST1，缩减到1的最小步问题：一个数n它的下一步可以减一，或者除以2（可以被2整除的前提下），或者除以3（可以被3整除的前提下）,问n最少要多少步才可以为1？

题目分析

　　简单的dp，但需要注意，由于本题是有多组数据，所以要一次性的把n等于1到20000000的值都求出来保存，然后根据输入的值进行打印

代码

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
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 20000002
int result[MAX_SIZE];
void dp() {
    result[1] = 0;
    for(int i = 2; i < MAX_SIZE; i++) {
        result[i] = result[i - 1] + 1;
        if(i % 2 == 0) {
            result[i] = (result[i] < (result[i / 2] + 1)) ? result[i] : (result[i / 2] + 1);
        }
        if(i % 3 == 0) {
            result[i] = (result[i] < (result[i / 3] + 1)) ? result[i] : (result[i / 3] + 1);
        }
    }
}
int main() {
    int T;
    scanf("%d", &T);
    dp();
    for(int i = 1; i <= T; i++) {
        int n;
        scanf("%d", &n);
        printf("Case %d: %d\n", i, result[n]);
    }
}