Sunday, March 25, 2012

[code] TIOJ - 1463 打不倒的樹木人

http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1463

code應該很好懂

注意一下條件判斷就好了


#include <stdio.h>
#include <string.h>

char s[10001];
long long dp[10001];
int l;
long long dfs(int n)
{
    if (dp[n] >= 0) {
        return dp[n];
    }
    if (s[n] == '0') {
        return dp[n] = 0;
    }
    if (n == l - 1) {
        return dp[n] = 1;
    }
    if (n == l - 2) {
        if (s[n] > '2' || s[n] == '2' && s[n + 1] > '6') {
            return dp[n] = dfs(n + 1);
        } else {
            return dp[n] = dfs(n + 1) + 1;
        }
    }
    if (s[n] > '2' || s[n] == '2' && s[n + 1] > '6') {
        return dp[n] = dfs(n + 1);
    }
    return dp[n] = dfs(n + 1) + dfs(n + 2);
}
int main()
{
    while (gets(s) != NULL) {
        if (strcmp(s, "0") == 0) {
            return 0;
        }
        l = strlen(s);
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", dfs(0));
    }
}
 

No comments:

Post a Comment