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

作者: wjyyy 分类: DP,搜索,解题报告 发布时间: 2018-06-24 08:04

点击量:15

 

   原来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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */