【題解】ZeroJudge d859: NOIP2001 1.数的计算

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d859

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
int N;
int ans = 1;

void dfs(int n){
	for (int i=1; i<= n/2; i++){
		ans++;
		dfs(i);
	}
}


int main(){
	cin >> N;
	dfs(N);
	cout << ans << '\n';
	return 0;
}

Python code (credit: Amy Chou)
【解題想法 1】DFS
執行結果:NA (80%),最後一筆測資TLE

import sys
sys.setrecursionlimit(100000)

def dfs(n):
    global ans
    for i in range(1, int(n/2)+1):
        ans += 1
        dfs(i)

N = int(input())
ans = 1
dfs(N)
print(ans)

Python code (credit: Amy Chou)
【解題想法 2】DP
執行結果:AC

N = int(input())
dp = [1 for i in range(1001)]
for i in range(2, N+1):
    if i % 2:
        dp[i] = dp[i-1]
    else:
        for j in range(1, i//2+1):
            dp[i] += dp[j]

print(dp[N])
分享本文 Share with friends