题解 P5743 【【深基7.习8】猴子吃桃】
UnyieldingTrilobite
2020-02-26 22:41:36
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=1$时$1=1$成立。
若$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$均成立。
所以······程序:
```cpp
#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.