首页 > 代码库 > hdu 2084

hdu 2084

2024-07-17 02:43:27   220人阅读

//Time Limit Exceeded

#include <iostream>
#define N 105      
#include<string.h>
using namespace std;
int a[N][N];
int n;
int max(int x, int y)
{  return x>y?x:y   ;      }

int maxsum(int i,int j)
{
 if(i==n-1)  return a[i][j];
 return a[i][j]+max(maxsum(i+1,j),maxsum(i+1,j+1));
}

int main()
{
  int c ;
 int i,j;
 cin>>c;
 while(c--)
 {
  cin>>n ;
  for(i=0;i<n;i++)
    for(j=0;j<=i;j++)  cin>>a[i][j];
   
  
         cout<<maxsum(0,0)<<endl;
 }
 
}

 

 

 

 

 

 

 

 

#include <iostream>
#define N 105      
#include<string.h>
using namespace std;
int a[N][N];
int n;
int s[N][N];
int max(int x, int y)
{  return x>y?x:y   ;      }

int maxsum(int i,int j)
{
 if(i==n-1)  return s[i][j]=a[i][j];
 return s[i][j]=a[i][j]+max(maxsum(i+1,j),maxsum(i+1,j+1));
}

int main()
{
  int c ;
 int i,j;
 cin>>c;
 while(c--)
 {
  cin>>n ;
  for(i=0;i<n;i++)
    for(j=0;j<=i;j++)  cin>>a[i][j];
   
  
         cout<<maxsum(0,0)<<endl;
 }
 
}

 

 

 

 

 

 

 

 

 

 

 

 

******************************************************************************88

 

 

 

 

#include <iostream>
#define N 105      
#include<string.h>
using namespace std;
int a[N][N];
int n;
int s[N][N];
int max(int x, int y)
{  return x>y?x:y   ;      }

int maxsum(int i,int j)
{
 if(i==n-1)  return s[i][j]=a[i][j];
     else if(s[i][j]!=-1)  return s[i][j];
     return s[i][j]=a[i][j]+max(maxsum(i+1,j),maxsum(i+1,j+1));
}

int main()
{
  int c ;
 int i,j;
 cin>>c;
 while(c--)
 {
    memset(s,-1,sizeof(s));
  cin>>n ;
  for(i=0;i<n;i++)
    for(j=0;j<=i;j++)  cin>>a[i][j];
   
  
         cout<<maxsum(0,0)<<endl;
 }
 
}

 

 

 

 

hdu 2084   记忆式搜索

#include <iostream>
#include <cstring>
#define N 100
using namespace std;
int a[N][N],n,s[N][N];
int maxsum(int i,int j)
{ if (i==n-1) return s[i][j]=a[i][j];
else if (s[i][j]!=-1) return s[i][j];  
else return s[i][j]=a[i][j]+max(maxsum(i+1,j),maxsum(i+1,j+1));
}
int main(int argc, char *argv[])
{ int i,j,c;
cin>>c;
while (c--)
{ cin>>n;
memset(s,-1,sizeof(s));
for (i=0;i<n; i++)
  for (j=0;j<=i; j++) cin>>a[i][j];
   cout<<maxsum(0,0)<<endl;
}
return 0;
}
 
 
 
 
 
 
 
 
 
 
********************************************************************************************************************************************************************************************
 
DP动态规划
 
 
 
 

#include <iostream>
#define N 100
using namespace std;
int a[N][N],n;
int dp( )
{ int i,j;
for (i=n-2;i>=0; i--)
  for (j=0; j<=i; j++)
    a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
}

int main(int argc, char *argv[])
{
  int i,j,c;
cin>>c;
while (c--)
{ cin>>n;
for (i=0;i<n; i++)
  for (j=0;j<=i; j++) cin>>a[i][j];
        dp();
   cout<<a[0][0]<<endl;
}
return 0;
}

 


联系
我们