Lightoj 1004 - Monkey Banana Problem-白红宇

Lightoj 1004 - Monkey Banana Problem

阅读量：5323 次

发布时间：2019-06-14

本文共 1004 字，大约阅读时间需要 3 分钟。

题目链接：http://acm.hust.edu.cn/vjudge/contest/121396#problem/F

密码：acm

分析：求从上往下路径的最大权值。

解题思路：数字三角形的变形，把菱形分为上下两部分求即可。dp[i][j]表示路径到第i行第j个点的最大权值和。

*：

上：dp[i][j]=max(dp[i-1][j], dp[i-1][j-1])+maps[i][j];

下：dp[i][j]=max(dp[i-1][j], dp[i-1][j+1])+maps[i][j];

Sample Input2476 42 5 109 8 12 22 12 78 210212 31Sample OutputCase 1: 63Case 2: 5

*********************************************************

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 8 using namespace std; 9 10 #define M 1020011 #define N 1500///N 开大了就MLE了，~~~~(>_<)~~~~ 12 13 int dp[N][N],maps[N][N];14 15 int main()16 {17 int n,i,j, T, k=1;18 19 scanf("%d", &T);20 21 while(T--)22 {23 scanf("%d", &n);24 25 memset(dp, 0,sizeof(dp));26 memset(maps,0,sizeof(maps));27 28 for(i=1;i<=n;i++)29 for(j=1;j<=i;j++)30 scanf("%d",&maps[i][j]);31 32 for(i=n+1;i