与班尼特·胡迪一起攻破浮空城 AC
Time Limit: 1 s Memory Limit: 256 MB
Description
桐人为了拯救被困在浮空城堡最顶层的亚丝娜,决定从第一层,不断战斗到最后一层,直至救出亚丝娜,但他需要班尼特·胡迪帮他设计一条攻略路线,可是班尼特·胡迪没有任何思绪,于是他找到了聪明的你帮忙。
现在把浮空城堡理想化为一个由h*n*m个的立方体区域组成的大方体,h为层数,1<=h<=100,n为纵向区域数量,1<=n<=100,m为横向区域数量,1<=m<=100。每个区域(非边缘区域)只与上下东南西北的六个区域相通,每个区域内有若干个守卫(不会超过10个),桐人一开始的战斗值p为0,每击败一个守卫,他的战斗值便会加1,击败守卫不消耗桐人的时间,击败完该区域所有守卫,他可以移动至与该区域相通的任何区域,每次移动时间一样。桐人的起始位置为第1层[n][1]区域,亚丝娜的位置为第h层[1][m]区域。
你设计的路线需满足以下条件:
1、桐人需要最快救出亚丝娜。
2、在保证最快救出亚丝娜的前提下,桐人需要尽可能多地击败守卫,以获取更多的战斗值,从而击败最后BOSS,救出亚丝娜。
Input
多组输入,第一行给出3个整数n、m,h, 接下去给出h张(第1层~第h层)n*m的区域守卫数量分布。
Output
输出一行桐人救出亚丝娜后最多能获得的战斗值p。
Samples
input:
3 3 1
0 2 0
0 4 0
0 0 5
4 5 2
0 0 3 2 0
0 5 3 0 0
6 0 0 1 0
0 1 7 0 0
0 9 0 0 0
0 5 0 0 0
0 0 0 0 0
1 0 0 2 0
output:
6 25
Hint
第二组样例中,
第一层地图为:
0 0 3 2 0
0 5 3 0 0
6 0 0 1 0
0 1 7 0 0
第二层地图为:
0 9 0 0 0
0 5 0 0 0
0 0 0 0 0
1 0 0 2 0
Author
Source
思路:从第一层左下角一直到h层右上角,沿途可以获得的最大值。
题解:首先要保证时间最短,所以前进的方向只有向上,向北和向东。其次,获得最大值需要用到动态dp。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
long long int n,m,h,i,j,k,a,b,c;
long long int p[][][]; //数据大,所以开long long
long long int dp[][][];
long long int max(long long int a,long long int b,long long int c)
{
return max(a,max(b,c));
}
int main()
{
while(scanf("%lld %lld %lld",&n,&m,&h)!=EOF)
{
memset(dp,,sizeof(dp));
for(i=;i<h;i++)
{
for(j=;j<n;j++)
{
for(k=;k<m;k++)
{
scanf("%lld",&dp[i][j][k]); //输入地图
}
}
}
for(i=;i<h;i++)
{
for(j=n-;j>=;j--)
{
for(k=;k<m;k++)
{ dp[i][j][k]+=max(dp[i-][j][k],dp[i][j+][k],dp[i][j][k-]); //最关键的一行,dp原来三种状态
/*for(a=0;a<h;a++)
{
for(b=0;b<n;b++)
{
for(c=0;c<m;c++)
{
printf("%lld ",dp[a][b][c]); //输出此时状态,用来检验
}
printf("\n");
}
}
printf("------------------------------------------\n");
*/
}
}
}
printf("%lld\n",dp[i-][][k-]); //输出到达亚斯娜所在地
}
return ;
}