参考代码:
#include <iostream>
using namespace std; typedef long long ll;
const ll maxn = + ;
ll dp[maxn]; int main() {
ll t, a, b, now;
dp[] = ;
dp[] = ;
for(int i = ; i <= maxn; i ++) {
dp[i] = dp[i - ] + dp[i - ];
}
cin >> t;
while(t --) {
cin >> a >> b;
now = b - a + ;
cout << dp[now] << endl;
}
return ;
}
参考代码:
/*
递推思想,很容易可以手推出3种情况,我们可以确定的是,在放第涂第n个格子的时候前n - 1个格子已经涂完了,所以对于第n个格子,我们分为以下两种情况
<1>:前n - 1个格子已经涂完了,涂的方法有dp[n - 1]种,我们确定第n - 1和第n个不同色,并且要求第n个和第一个不同色,所以第n个只有一种图法,乘法规律我们知道在确定前n - 1种格子的涂法时第n个有dp[n - 1]种图法。
<2>:前n - 2个格子已经涂完了,涂的方法有dp[n - 2]种,这时我们知道,第n - 1个格子的颜色肯定是与第一个格子相同的,因为如果他们不同,则第n个格子又只有一种图法,和情况一是一样的,第n个格子我们有两种图法,所以由乘法规律的在提前确定n - 2个格子的涂法时第n个格子有2 * dp[n - 2]种涂法。
*/
#include <cstdio>
using namespace std; typedef long long ll;
const int maxn = + ;
ll dp[maxn]; int main() {
int n;
dp[] = ;
dp[] = ;
dp[] = ;
for(int i = ; i <= maxn; i ++) {
dp[i] = dp[i - ] + * dp[i - ];
}
while(~scanf("%d", &n)) {
printf("%lld\n", dp[n]);
}
return ;
}