晋江科技馆集训Day 2

PS: This is a note.

递推与递归

详细可见我之前的那篇博客

递推和递归例题

e.g. 走台阶

#include <bits/stdc++.h>
using namespace std;
int n,k,f[100005];
int main() {
	cin>>n>>k;
	f[1]=1;
	for(int i=2; i<=n; i++) {
		if(i<=k) {
			for(int j=1; j<k; j++) {
				f[i]=(f[i]+f[j])%100003;
			}
			f[i]++;
		} else for(int j=i-k; j<i; j++) {
				f[i]=(f[i]+f[j])%100003;
			}
	}
	cout<<f[n];
	return 0;
}

e.g. 分裂的细菌

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,sum[21]= {0};
	cin>>n;
	sum[0]=1;
	for (int i=1; i<=n; i++) {
		if(i<=3) {
			sum[i]=sum[i-1];
		} else {
			sum[i]=sum[i-1]+sum[i-3];
		}
	}
	cout<<sum[n];
	return 0;
}

e.g. 成虫数

贪心

贪心例题

e.g. 最短路径