题解 P5743 【【深基7.习8】猴子吃桃】

· · 题解

upd：修复一个推导错误（结论无误）。

来讲一种O(1)算法（可能超出新手范围？）

动态规划。

设ans_i表示n=i时的答案。

显然ans_1=1（如果不明白······建议重新读题。）.

怎么转移？

列方程\frac{ans_i}{2}-1=ans_{i-1}.

解得ans_i=2(ans_{i-1}+1).

前方高能。

归纳ans_n=3\times 2^{n-1}-2.

若$n=k$时成立，即$ans_k=3\times 2^{k-1}-2

则对于n=k+1,ans_{k+1}=2(ans_k+1)=2(3\times 2^{k-1}-2+1)=3\times 2^{k}-2.

也成立。

所以对于一切正整数n均成立。

所以······程序：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    cout<<(1<<n-1)*3-2;
    return 0;
}

怎么想到？两种方法：

第一：动态规划打表找规律+归纳。

第二：把递推公式的ans_{i-1}继续展开，会得到一串等比数列，求和化简+归纳即可。

Over.