题解 | #汽水瓶#

#include <stdio.h>
//使用动态规划解决问题
int maxnum(int a)
{
    int res=0,i=2;
    int dp[500];
    dp[1]=a/3+a%3;
    res=a/3;
    for(i=2;dp[i-1]>1;i++)
        if(dp[i-1]>2)
        {
            dp[i]=dp[i-1]/3+dp[i-1]%3;
            res+=dp[i-1]/3;
        } else if(dp[i-1]==2)
        {
            dp[i]=1;
            res+=1;
        }
    
    return res;
}

int main() {
    int num,flag=0;
    while (scanf("%d", &num) != EOF) {  
        if(num!=0)
        {
            flag = maxnum(num);
            printf("%d\n",flag);
        }
        
    }
    return 0;
}

解题思路：

可以将换汽水瓶分为i次兑换，设dp[i]为第i次兑换后剩余的空汽水瓶数。而第i次兑换后所剩的空汽水瓶数依赖于第i-1次所剩的空汽水瓶数。这样就能得到一个状态转移方程式(dp[i]=1作为临界条件)：

dp[1]=原始空汽水瓶数量m/3;

当dp[i-1]>2时，

dp[i]=dp[i-1]/3+dp[i-1]%3;

当dp[i-1]=2

dp[i]=1

然后使用一个变量res来统计可兑换的汽水数量。