Lucifer's Pyramid of Numbers
Time
Limit: 1000MS
Memory
Limit: 40000KB
Submissions: 4
Accepted: 0
Description
Lucifer has a strange hobby, he sometimes put offending evils to the
Pyramid of Numbers (PoN), and then decides whether he will liberate the evils or
not through a game.In PoN, the poor evil could only move straightly down or
bottom-right step by step. An evil, the sum of numbers on whose moving path is
the biggest one among all probable sums, will be liberated and otherwise it will
be killed.Aiushtha (EH, Enchant, 魅惑魔女) has been arrested by Lucifer because she
always say “I’m game!” in DotA but Lucifer took the pet phrase as “I’m gay!”.
What’s more, Lucifer improves the degree of difficulty since EH is smart. He
gives EH a once only tool and in a particular step, EH could move to any point
in the nether adjacent level she wants by one step.
Your task is to calculate the biggest number that Aiushtha can
get.
Input
THERE ARE MULTIPLE TESTCASES.
The first line of each testcase is a number N(0<=N<=1000).
The following N lines describes the PoN as the Sample Input. Each number
appeared is in the range from -1000 to 1000.
(-1000<=number<=1000)
Output
the sum
Sample
Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample
Output
35
Hintt
Source
我的代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define inf 0x3f3f3f
int m[1010][1010],dp1[1010][1010];
int n;
int max2(int a,int b)
{ if(a>b) return a;
return b;
}
int max1(int k)
{ int i; int max=-inf;
for(i=1; i<=k+1; i++)
{ if(max<dp1[k+1][i])
max=dp1[k+1][i]; }
return max;
}
int main()
{ int i,j,k,max,t;
while(scanf("%d",&n)!=EOF)
{ max=-inf;
for(i=1; i<=n; i++)
{ for(j=1; j<=i; j++)
{ scanf("%d",&m[i][j]);
if(i==n)
dp1[i][j]=m[i][j]; }
}
for(k=2; k<=n-1; k++)
{ if(k==2) i=n-1;
else
i=k;
for(; i>=1; i--)
{ if(i==k) t=max1(k);
for(j=1; j<=i; j++)
{
if(i==k)
{ dp1[i][j]=t+m[i][j]; }
else { dp1[i][j]=max2(dp1[i+1][j],dp1[i+1][j+1])+m[i][j]; }
} }
if(dp1[1][1]>max)
max=dp1[1][1];
}
printf("%d\n",max);
}
return 0;
}
Time
Limit: 1000MS
Memory
Limit: 40000KB
Submissions: 4
Accepted: 0
Description
Lucifer has a strange hobby, he sometimes put offending evils to the
Pyramid of Numbers (PoN), and then decides whether he will liberate the evils or
not through a game.In PoN, the poor evil could only move straightly down or
bottom-right step by step. An evil, the sum of numbers on whose moving path is
the biggest one among all probable sums, will be liberated and otherwise it will
be killed.Aiushtha (EH, Enchant, 魅惑魔女) has been arrested by Lucifer because she
always say “I’m game!” in DotA but Lucifer took the pet phrase as “I’m gay!”.
What’s more, Lucifer improves the degree of difficulty since EH is smart. He
gives EH a once only tool and in a particular step, EH could move to any point
in the nether adjacent level she wants by one step.
Your task is to calculate the biggest number that Aiushtha can
get.
Input
THERE ARE MULTIPLE TESTCASES.
The first line of each testcase is a number N(0<=N<=1000).
The following N lines describes the PoN as the Sample Input. Each number
appeared is in the range from -1000 to 1000.
(-1000<=number<=1000)
Output
the sum
Sample
Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample
Output
35
Hintt
Source
我的代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define inf 0x3f3f3f
int m[1010][1010],dp1[1010][1010];
int n;
int max2(int a,int b)
{ if(a>b) return a;
return b;
}
int max1(int k)
{ int i; int max=-inf;
for(i=1; i<=k+1; i++)
{ if(max<dp1[k+1][i])
max=dp1[k+1][i]; }
return max;
}
int main()
{ int i,j,k,max,t;
while(scanf("%d",&n)!=EOF)
{ max=-inf;
for(i=1; i<=n; i++)
{ for(j=1; j<=i; j++)
{ scanf("%d",&m[i][j]);
if(i==n)
dp1[i][j]=m[i][j]; }
}
for(k=2; k<=n-1; k++)
{ if(k==2) i=n-1;
else
i=k;
for(; i>=1; i--)
{ if(i==k) t=max1(k);
for(j=1; j<=i; j++)
{
if(i==k)
{ dp1[i][j]=t+m[i][j]; }
else { dp1[i][j]=max2(dp1[i+1][j],dp1[i+1][j+1])+m[i][j]; }
} }
if(dp1[1][1]>max)
max=dp1[1][1];
}
printf("%d\n",max);
}
return 0;
}
