学步园

昨天晚上腾讯马拉松编程的第一场比赛的最后一题：

昨天晚上没能做出来，看上去感觉是背包不错。但是想破头皮都没有想出来。今天上午发现已经有解题报告了，看了解题报告才知道原来这种算法叫做背包最优方案数。不枉做了一晚上啊，总算是有点收获了。

下面是我AC的代码。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int main()
{
    int A, B, t;
    long long f[2][205];
    while(scanf("%d%d%d", &A, &B, &t) != EOF)
    {
        memset(f, 0, sizeof(f));
        int r = t / 15;
        int mid = r / 2;
        r -= mid;
        B += mid;
        int sub = B - A;
        bool k = 0;
        f[0][0] = 1;
        for(int i = 1; i <= r; ++i)
        {
            for(int j = i - 1; j <= (i - 1) * 3; ++j)
            {
                if(f[k][j])
                {
                    f[k ^ 1][j + 1] += f[k][j];
                    f[k ^ 1][j + 2] += f[k][j];
                    f[k ^ 1][j + 3] += f[k][j];
                }
            }
            memset(f[k], 0, sizeof(int) * 205);
            k ^= 1;
        }
        long long ans = 0;
        for(int j = max(r, sub + 1); j <= 3 * r; ++j)
            ans += f[k][j];
        cout << ans << endl;
    }
    return 0;
}