y总的方法果然好用!
状态表示:为了求出购买n瓶饮料最后可以换购到几瓶(用$f(n)$表示),我们可以先推演一下换购的情况:买了n瓶,那么第一次用所有的瓶盖去换购,得到$(n/3)$瓶饮料,加上$(n \bmod 3)$个瓶盖,又可以进行下一次的换购。那么,我们要求的n瓶饮料的状态可以用这个公式表示:
$$ f(n)=n/3+f(n/3+n \bmod 3) $$
再使用滚动数组把它表示出来就可以AC了。
为什么使用滚动数组?自底向上方法,时间复杂度为$O(n)$,如果直接使用递归,那么会导致重复的计算,时间复杂度大大增加。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;cin>>n;
int arr[10100]={};
memset(arr,0,sizeof(arr));
for(int i=1;i<=n;i++)
{
arr[i]=arr[i%3+i/3]+i/3;
}
cout<<arr[n]+n;
return 0;
}