与班尼特·胡迪一起攻破浮空城 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。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 long long int n,m,h,i,j,k,a,b,c;
 8     long long int p[105][105][105];           //数据大，所以开long long
 9     long long int dp[105][105][105];
10 long long int max(long long int a,long long int b,long long int c)
11 {
12     return max(a,max(b,c));
13 }
14 int main()
15 {
16     while(scanf("%lld %lld %lld",&n,&m,&h)!=EOF)
17     {
18         memset(dp,0,sizeof(dp));
19         for(i=0;i<h;i++)
20         {
21             for(j=0;j<n;j++)
22             {
23                 for(k=0;k<m;k++)
24                 {
25                     scanf("%lld",&dp[i][j][k]);            //输入地图
26                 }
27             }
28         }
29         for(i=0;i<h;i++)
30         {
31             for(j=n-1;j>=0;j--)
32             {
33                 for(k=0;k<m;k++)
34                 {
35 
36                     dp[i][j][k]+=max(dp[i-1][j][k],dp[i][j+1][k],dp[i][j][k-1]);       //最关键的一行，dp原来三种状态
37                     /*for(a=0;a<h;a++)
38                     {
39                         for(b=0;b<n;b++)
40                             {
41                                 for(c=0;c<m;c++)
42                                     {
43                                         printf("%lld ",dp[a][b][c]);            //输出此时状态，用来检验
44                                     }
45                                 printf("\n");
46                             }
47                     }
48                     printf("------------------------------------------\n");
49                     */
50                 }
51             }
52         }
53         printf("%lld\n",dp[i-1][0][k-1]);         //输出到达亚斯娜所在地
54     }
55     return 0;
56 }