猴子3202 ACM 基础训练

在hphp还没有电脑的时候，手机是她唯一的娱乐工具，最喜欢玩的游戏就是猴子，猴子的行动范围是在n(n<=100)根水平排列的柱子的底端上，并且以坐虫子为快乐。每坐到一个虫子他就快乐一点。可是他的快乐是有极限的，因为他只能水平的在相邻的柱子间移动，并且移动一次时间是1s，如果在时间t(0<=t<=10000)猴子刚好在柱子m（1<=m<=n）上并且此时m上恰好会出现一只虫子，那么猴子就可以坐到它了。现在猴子最初(0s)在1号柱子上,在t时间m柱子上是否能有虫子以一个矩阵给出。猴子想要最快乐，你是否能够帮助它呢~

Input

多组测试数据，每组测试数据首先给出整数n，t (0<n<=100，0<=t<=10000)占一行。n表示总共有多少柱子，t表示游戏结束的时间，t时间猴子就不可以再坐虫子咯。接下来有n行，每行有t个整数（0或1）T0,T2....Tt-1。第i行第j个数字表示第i个柱子在j时间是否有虫子出现。

Output

对于每组测试数据输出一个整数，表示猴子快乐的最大点数。

Sample Input

3 4
0 1 0 1
1 0 0 1
1 1 1 1
3 4
1 0 1 0
1 1 1 0
1 1 1 1
1 5
1 0 1 0 1

Sample Output

2
4

3

#include "iostream"
#include "string.h"
#include "stdio.h"
using namespace std;
#define Max 1000
#define Sky 1<<29
int Dp[Max][Max];
int Map[Max][Max]; 
#define MAX(a,b,c) ((a>b?a:b)>c?(a>b?a:b):c)
int N,T;
int main()
{  
    //freopen("1.txt","r",stdin);
    
    cin>>N>>T;
    for(int i=1;i<=N;i++)
    for(int j=0;j<T;j++)
    cin>>Map[i][j]; 
	memset(Dp,0,sizeof(Dp));
	Dp[0][1]=Map[1][0];
   
    for( i=1;i<T;i++) //Dp[i][j] 第i时间在j柱子上 
    {
    	for( int  j=1;j<=N && j<=i+1;j++)
    	{    
    	     int a,b,c;
    	     a=b=c=-Sky;

    	     a=Dp[i-1][j];
    		 if(j>1)
    		 b=Dp[i-1][j-1];
    		 if(j<N)
    		 c=Dp[i-1][j+1];
    		 Dp[i][j]=MAX(a,b,c)+Map[j][i];
			 //	 //因为时间在动，所以在Dp[i][j]  时，猴子到的地方是 Map[j][i] 
    		
    	}
    }
     
    int M=0;
    for(  i=1;i<=N;i++)
    { 
       if(Dp[T-1][i]>M)
       M=Dp[T-1][i];
    }
    
    cout<<M<<endl;

	 
	return 0;
}