noip模拟赛 蒜头君的坐骑

分析：标准的棋盘dp问题.

      如果没有技能，那么就很好做了，相当于传纸条的做法.有了技能的限制，我们就要加上一维表示用了多少次技能，这个时候转移就要用到dfs了，而且不能用填表法，要用刷表法，从当前位置用技能的状态来更新到达的位置的状态,dp状态转移方程也要写成刷表法的形式.

如果很难从以前的状态推得现在的状态，那么就用现在的状态去更新以后的状态吧！

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int inf = 0x7ffffff;

int n, m, t, k, h, atk,f[510][510][11],a[510][510],ans = inf;

int jisuan(int xue, int gongji)
{
    return(h - 1) / gongji * xue;
}

void dfs(int x,int y,int cur,int xue,int gongji,int depth)
{
    if (depth > k)
    {
        f[x][y][cur + 1] = min(f[x][y][cur + 1], xue);
        return;
    }
    if (x + 1 <= n)
        dfs(x + 1, y, cur, xue + jisuan(a[x + 1][y],gongji + a[x + 1][y]), gongji + a[x + 1][y], depth + 1);
    if (y + 1 <= m)
        dfs(x, y + 1, cur, xue + jisuan(a[x][y + 1], gongji + a[x][y + 1]), gongji + a[x][y + 1], depth + 1);
}

int main()
{
    scanf("%d%d%d%d%d%d", &n, &m, &t, &k, &h, &atk);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int l = 0; l <= t; l++)
                f[i][j][l] = inf;
    f[1][1][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int l = 0; l <= t; l++)
            {
                if (l != t)
                    dfs(i, j, l, f[i][j][l], atk,1);
                if (i + 1 <= n)
                    f[i + 1][j][l] = min(f[i + 1][j][l], f[i][j][l] + jisuan(a[i + 1][j], atk));
                if (j + 1 <= m)
                    f[i][j + 1][l] = min(f[i][j + 1][l], f[i][j][l] + jisuan(a[i][j + 1], atk));
            }
    for (int i = 0; i <= t; i++)
        ans = min(ans, f[n][m][i]);
    printf("%d
", ans);

    return 0; 
}