POJ3790 记忆化搜索, DP

简单DP?, 记忆化搜索过的;

不过数据是真的感觉还是比较水的; 比赛时用的 long long , 开的1e6的数组, ; 下来发现1e3的也能过 ...

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e3 + 5;
int dp[maxn];

int dfs(int xx){
    if(dp[xx] != 0) return dp[xx];
    int ans = 1, x = xx;
    for(int i=1;x > 1;x-=2, i++){
        ans += dfs(i);
    }
    dp[xx] = ans;
    return ans;
}

int main(){
    int n, x;
    scanf("%d", &n);
    dp[0] = dp[1] = 1;
    for(int cas = 1;cas<=n;cas++){
        scanf("%d", &x);
        printf("%d %d\n", cas, dfs(x));
    }
    return 0;
}