学步园

    第五题：整数划分  
    dp[m] += dp[m - i](i = 1,2,3)
    
      
    #include <stdio.h>  
    #include <string.h>  
    #include <iostream>  
    #include <algorithm>  
    using namespace std;  
    #define INF 100000000  
    #define MAXN 200  
    long long dp[2][MAXN + 1];  
    int main()  
    {  
        int A, B, t;  
        int now , pre;  
        while(~scanf("%d%d%d", &A, &B, &t))  
        {  
            int n = t / 15;  
            B += n / 2;  
            n = (n + 1) / 2;  
            int m = B - A + 1;  
      
            if(n == 0)  
                {  
                     if(A>B)printf("1\n");  
                     else printf("0\n");  
                        continue;  
                }  
            memset(dp, 0, sizeof(dp));  
            now = 0;  
            pre = 1;  
            dp[now][1] = dp[now][2] = dp[now][3] = 1;  
            for(int i = 2; i <= n; ++i)  
            {  
                now = !now;  
                pre = !pre;  
                for(int j = MAXN; j >= 0; --j)  
                {  
                    dp[now][j + 1] += dp[pre][j];  
                    dp[now][j + 2] += dp[pre][j];  
                    dp[now][j + 3] += dp[pre][j];  
                }  
                memset(dp[pre], 0, sizeof(dp[pre]));  
            }  
            long long ans = 0;  
            for(int i = (m > n) ? m : n; i <= MAXN; ++i )  
                ans += dp[now][i];  
            printf("%lld\n", ans);  
        }  
        return 0;  
    }