HDU5234 – Happy birthday(DP)

题目链接：HDU5234

【题意】

很久很久以前，有一个叫Jack的枪手。他非常喜欢打猎。一天，他去了一个小树林。那儿有n只鸟，还有n棵树。第i只鸟站在第i棵树的顶端。这些树从左到右排成一条直线。每一棵树都有它的高度。Jack站在最左边那棵树的左边。当Jack在高度为H的地方向右发射一棵子弹时，站在高度为H的树上且离Jack最近的鸟儿就会落下来。
Jack会射击多次，他想知道每次射击哪只鸟儿会落下来。

【分析】很简单的DP题，dp[x][y][w][2]表示当前在点(x,y)获得了w重量并且当前点是否吃掉时获得的最大重量；我用记忆化写了。

【AC CODE】202ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100+10;
const int f[2][2]={{1,0},{0,1}};
int a[MAXN][MAXN], dp[MAXN][MAXN][MAXN][2],n,m,k;

int dfs(int x, int y, int w, bool eat)
{
    int &ans = dp[x][y][w][eat];
    if(~ans) return ans;
    if(x == n-1 && y == m-1)
    {
        return 0;
    }
    ans = 0;
    rep(i,0,2)
    {
        int ni = x+f[i][0], nj = y+f[i][1];
        if(0 <= ni && n > ni && 0 <= nj && m > nj)
        {
            int tmp = 0;
            if(w+a[ni][nj] <= k)
                tmp = dfs(ni,nj,w+a[ni][nj],1)+a[ni][nj];
            if(tmp <= k) ans = max(tmp,ans);
            tmp = dfs(ni,nj,w,0);
            if(tmp <= k) ans = max(tmp,ans);
        }
    }
    return ans;
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    while(~scanf("%d %d %d%*c", &n, &m, &k))
    {
        clc(dp,-1);
        rep(i,0,n)
        {
            rep(j,0,m)
                scanf("%d%*c", &a[i][j]);
        }
        int ans = dfs(0,0,0,0);
        //clc(dp,-1);
        int tmp = 0;
        if(a[0][0] <= k)
            tmp = dfs(0,0,a[0][0],1)+a[0][0];
        if(tmp <= k) ans = max(ans,tmp);
        printf("%d\n", ans);
    }
    return 0;
}