题目链接: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=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
cin>>a[i][j];
}
}
} void init()
{
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
for(int k=;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+,y,tot,step+,atk+a[x+][y],dam+((h-)/(atk+a[x+][y])*a[x+][y]));
dfs(x,y+,tot,step+,atk+a[x][y+],dam+((h-)/(atk+a[x][y+])*a[x][y+]));
} void solve()
{
init();
dp[][][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
for(int p=;p<=t;p++)
{
if(dp[i][j][p]>=INF) continue;
if(i+<=n) dp[i+][j][p]=min(dp[i+][j][p],dp[i][j][p]+((h-)/atk)*a[i+][j]);
if(j+<=m) dp[i][j+][p]=min(dp[i][j+][p],dp[i][j][p]+((h-)/atk)*a[i][j+]);
if(p<t) dfs(i,j,p+,,atk,dp[i][j][p]);
}
}
}
} void print()
{
int minn=INF;
for(int i=;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();
}