计蒜客 16447 蒜头君的坐骑 题解【DP】【搜索】

点击量：148

   原来DP还分刷表法和填表法啊……

目录

题目描述

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

 

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

 

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

 

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

 

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

 

输入输出格式

输入格式：

第一行六个正整数n,m,t,k,h,atk，n,m表示地图长度、宽度，t表示人马技能可使用次数，k表示人马技能持续移动次数，h,atk表示每只怪物的体力和人马的初始攻击力。保证 n+m−1≥t×k。

 

接下来n行，每行m个整数，表示每个点的怪物的攻击力。保证 (1,1) 点、(n,m) 点为 0，其他点为正整数。

 

输出格式：

输出一个整数，表示蒜头君受到的最小伤害。

 

输入输出样例

输入样例#1：

4 3 2 1 7 4

0 2 4 3

5 1 2 3

2 5 4 0

输出样例#1：

3

说明

对于30%的测试数据，满足 1≤n,m≤10, 1≤t≤3, 1≤k≤3；

 

对于60%的测试数据，满足 1≤n,m≤100, 1≤t≤10, 1≤k≤5；

 

对于100%的测试数据，满足1≤n,m≤500, 1≤t≤10, 1≤k≤5, 1≤atk≤h≤100, 1≤怪物攻击力≤100。

   看上去是一个棋盘DP，不过有buff就不好写。但是buff是和DP方向相同的，因此把buff放在dfs里去做，来更新buff结束时的状态，就比较简单了。

   首先，我们看到主角是先手，那么在某一轮中NPC死了，NPC就不会攻击，那么伤害计算公式为（a[][]是攻击力）$ \lfloor \frac{h-1}{atk}\rfloor $。

   我们可以试着拿5维来存一下状态：f[i][j][k][l][t]，表示坐标为(i,j)，此时已经用了k次技能，走了技能的第l步，此时攻击力为t。这样确实可做，只不过空间开销太大。如果压掉一维（第一维）是可以勉强接受的，不过依然是5维的时间复杂度仍然吃不消。

   这里我们注意到每次使用技能中间不能停下，而且技能和DP方向相同，那么我们在使用技能时，只管，也只能管起点和终点，半路上是不能更新的。在这种棋盘DP中，我们就可以用dfs来简化这个过程。而dfs的状态就很好存了，可以将当前攻击力、路上受到的伤害存储在全局变量里，dfs是很好完成的。当dfs迭代k层后，更新目标点的状态，这样层次感就很明显了。

   从而我们有了DP状态:f[i][j][k]表示在坐标为(i,j)的点，已经使用了k次技能时的最小伤害。

   这里我们应该用刷表法而不是填表法，因为枚举状态比较好枚举，但是不好控制来时的状态（如果细节处理到位也是可以实现的）。因此我们对每个点，去转移它能到达的点，这样状态就会简单许多。对于不用技能的，每个点可以到它右边的或下边的，在转移过程中计算伤害就好了。如果使用技能，用一次dfs来搜索，找到终点，将最后一维+1并计算伤害，状态转移。

   一道经典的DP套搜索的好题。

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
int n,m,t,h,k,atk;
int a[510][510];
int f[510][510][12];
int Atk,sum,fromx,fromy,fromt;
void dfs(int x,int y,int num)
{
    int delta=h/Atk-1;
    if(h%Atk)
        delta++;
    sum+=a[x][y]*delta;
    if(num==k)
    {
        f[x][y][fromt+1]=min(f[x][y][fromt+1],f[fromx][fromy][fromt]+sum);
        sum-=a[x][y]*delta;
        return;
    }
    if(x<n)
    {
        Atk+=a[x+1][y];
        dfs(x+1,y,num+1);
        Atk-=a[x+1][y];
    }
    if(y<m)
    {
        Atk+=a[x][y+1];
        dfs(x,y+1,num+1);
        Atk-=a[x][y+1];
    }
    sum-=a[x][y]*delta;
}
int main()
{
    memset(f,0x3f,sizeof(f));
    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]);
    f[1][1][0]=0;
    int delta;
    if(atk==0)
        delta=0;
    else
    {
        delta=h/atk;
        if(h%atk)
            delta++;
        delta--;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int l=0;l<=t;l++)
            {
                if(i<n)
                {
                    f[i+1][j][l]=min(f[i+1][j][l],f[i][j][l]+a[i+1][j]*delta);
                    if(l<t)
                    {
                        fromx=i;
                        fromy=j;
                        fromt=l;
                        Atk=atk+a[i+1][j];
                        sum=0;
                        dfs(i+1,j,1);
                    }
                }
                if(j<m)
                {
                    f[i][j+1][l]=min(f[i][j+1][l],f[i][j][l]+a[i][j+1]*delta);
                    if(l<t)
                    {
                        fromx=i;
                        fromy=j;
                        fromt=l;
                        Atk=atk+a[i][j+1];
                        sum=0;
                        dfs(i,j+1,1);
                    }
                }
            }
    int ans=99999999;
    for(int i=0;i<=t;i++)
        if(f[n][m][i]<ans)
            ans=f[n][m][i];
    printf("%d\n",ans);
    return 0;
}