题解 | #汽水瓶#

思路

由题意可知：

• n=0 的时候，有 0 瓶
• n=1 的时候，有 0 瓶
• n=2 的时候，有 1 瓶
• n=3 的时候，有 1 瓶
• n=4 的时候，有 2 瓶
• ......

由此，我们设 f(n) 为小明手上有 n 个空瓶的时候，可以得到的汽水瓶数。根据规则我们可以知道 f(n) = f(n/3+n%3) + n/3； 所以，自底向上即可计算出结果。

代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    vector<int> nums(101);
    nums[0] = 0;
    nums[1] = 0;
    nums[2] = 1;
    while( true )
    {
        cin >> n;
        if( 0 == n )
            break;
        if( n < 3 )
            cout << nums[n] << endl;
        else
        {
            for( int i = 3; i <= n; i++ )
            {
                int tmp = i / 3;
                nums[i] = nums[tmp+i%3] + tmp;
            }
            cout << nums[n] << endl;
        }
    }
    return 0;
}