xmu1010

这个题目算法真的说不上，可能跟动态规划扯上点关系，但这个很简单。

CODE:

 

#include<iostream>
#include<cstdlib>
#define max 1000
int array[max][max];

using namespace std ;

void maxmun(int number)
{
     int temp=0 ;
     for(int i=0;i<number;i++)
     temp =temp>array[number-1][i]?temp:array[number-1][i];
     cout<<temp<<endl;
}

int twomax(int a , int b )
{
    return a>b?a:b;
}

void chan(int n )
{
  if(n==2) {
  array[1][0]=array[1][0]+array[0][0];
  array[1][1]=array[1][1]+array[0][0];
  }
  else if(n>2){
            for(int i=1;i<n-1;i++)
                array[n-1][i]=twomax(array[n-1][i]+array[n-2][i-1],array[n-1][i]+array[n-2][i]);
                array[n-1][0]=array[n-1][0]+array[n-2][0];
                array[n-1][n-1]=array[n-1][n-1]+array[n-2][n-2];
              }
}
           
int main()
{
    int number ;
    cin>>number ;
    for(int i=0;i<max;i++)
       for(int j=0;j<max;j++)
          array[i][j]= 0 ;
    for(int i=0;i<number;i++)
       for(int j=0 ;j<=i;j++)
           cin>>array[i][j];
    for(int i=1 ;i<=number;i++)
    chan(i);
    maxmun(number);
    system("pause");
    return 0 ;
}