首页 > 代码库 > hdu 2084
hdu 2084
//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>
#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;
}