hdu4504 篮球梦

题意：略

分析：记忆化搜索

用dp[i][j] 表示 i 次攻击得到少于j分的方案

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

using namespace std;

const int N = 20 + 5;
const int M = 600 + 10;

__int64 f[N];
__int64 dp[N][M];

int s[3] = {1, 2, 3};

void init()
{
    f[0] = 1;
    f[1] = 3;
    for(int i = 2; i < N; ++i)
        f[i] = f[i - 1] * 3;
}

__int64 dfs(int depth, int score)
{
    if(dp[depth][score] != -1) 
        return dp[depth][score];
    if(depth == 1)
    {
        int sum = 0;
        for(int i = 0; i < 3; ++i)
            if(score > s[i])
                ++sum;
        return dp[depth][score] = sum;
    }
    __int64 ret = 0;
    for(int i = 0; i < 3; ++i)
    {
        if(score > s[i])
            ret += dfs(depth - 1, score - s[i]);
    }
    return dp[depth][score] = ret;
}

int main()
{
    int A, B, t;
    init();
    while(scanf("%d %d %d", &A, &B, &t) == 3)
    {
        int tot = t / 15;
        B += tot / 2;
        int n = tot - tot / 2;//我方还能进攻的次数
        int m = B - A + 1;//我方比B队少的分数

        if( m <= 0){//已经赢了
            printf("%I64d\n",f[n]);
            continue;
        }

        if(m > n * 3) {
            printf("0\n");
            continue;
        }
        memset(dp, -1, sizeof(dp));
        printf("%I64d\n",f[n] - dfs(n, m));
    }
    return 0;
}