计蒜客模拟赛D1T3 蒜头君的坐骑：用dfs转移dp

题目链接：https://nanti.jisuanke.com/t/16447

题意：

　　蒜头君有一只坐骑，人马。

　　一天，蒜头君骑着他的坐骑走上了一片n*m的大荒野，一开始时，蒜头君在(1,1)点，他要前往(n,m)点，蒜头君的人马每次可以向右或向下移动一格。然而这片荒野并不平静，除了起点和终点外每个点都有一只怪物会袭击蒜头君。

　　然而蒜头君的人马强大无比，它会先对怪物造成等同于它攻击力的伤害，然后蒜头君才会受到怪物的攻击，伤害等同于怪物的攻击力。然后人马再攻击怪物，怪物再攻击蒜头君，直至怪物死去，假设每个怪物具有相同的体力。

　　此外，蒜头君的人马还有一个强大无比的技能，使用该技能会使蒜头君接下来 k次移动，每一次移动后增加等同于移动到的格子的怪物的攻击力，k次移动后，人马攻击力恢复至初始攻击力。人马必须在当前一个技能释放完后才可以释放下一个技能，且一共可释放技能的次数有限，那么试问蒜头君从起点到终点最少受到多少点伤害。

　　注意：蒜头君的体力是无限的。

题解：

　　用dp[i][j][p]表示在(i , j)点已经用完了p次技能时的最小伤害。

　　用us[i][j][p]表示在(i , j)点已经正在用第p次技能时的最小伤害。

　　那么到终点的最小伤害值 = min( min{dp[n][m][p]} , min{us[n][m][p]} )　　(枚举p：0 <= p <= t)

　　接下来考虑如何转移。

　　现在在(i , j)点，要么不用技能，要么用技能。

　　① 如果不用技能，那就直接转移：

　　　　dp[i+1][j] = min(dp[i+1][j] , dp[i][j] + 在(i+1 , j)点受到的伤害值)

　　　　dp[i][j+1] = min(dp[i][j+1] , dp[i][j] + 在(i , j+1)点受到的伤害值)

　　② 如果用技能，那么用dfs转移到每一个可能的用完这次技能的终点，同时在dfs中更新us数组的值。

AC Code：

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 505
#define MAX_T 15
#define INF 10000000

using namespace std;

int n,m,t,k,h,atk;
int a[MAX_N][MAX_N];
int dp[MAX_N][MAX_N][MAX_T];
int us[MAX_N][MAX_N][MAX_T];

void read()
{
    cin>>n>>m>>t>>k>>h>>atk;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
}

void init()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<=t;k++)
            {
                dp[i][j][k]=INF;
                us[i][j][k]=INF;
            }
        }
    }
}

void dfs(int x,int y,int tot,int step,int atk,int dam)
{
    us[x][y][tot]=min(us[x][y][tot],dam);
    if(step==k)
    {
        dp[x][y][tot]=min(dp[x][y][tot],dam);
        return;
    }
    dfs(x+1,y,tot,step+1,atk+a[x+1][y],dam+((h-1)/(atk+a[x+1][y])*a[x+1][y]));
    dfs(x,y+1,tot,step+1,atk+a[x][y+1],dam+((h-1)/(atk+a[x][y+1])*a[x][y+1]));
}

void solve()
{
    init();
    dp[1][1][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int p=0;p<=t;p++)
            {
                if(dp[i][j][p]>=INF) continue;
                if(i+1<=n) dp[i+1][j][p]=min(dp[i+1][j][p],dp[i][j][p]+((h-1)/atk)*a[i+1][j]);
                if(j+1<=m) dp[i][j+1][p]=min(dp[i][j+1][p],dp[i][j][p]+((h-1)/atk)*a[i][j+1]);
                if(p<t) dfs(i,j,p+1,0,atk,dp[i][j][p]);
            }
        }
    }
}

void print()
{
    int minn=INF;
    for(int i=0;i<=t;i++)
    {
        minn=min(minn,dp[n][m][i]);
        minn=min(minn,us[n][m][i]);
    }
    cout<<minn<<endl;
}

int main()
{
    read();
    solve();
    print();
}