用cin居然比scanf效率低了10倍,真有点不可思议。。。。。
#include<stdio.h>
#include<string.h>
int N;
int number[5100];
int dp[5100];
int max(int a,int b){return a>b?a:b;}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int i,j;
scanf("%d",&N);
for(i=1;i<=N*(N+1)/2;i++)
{
scanf("%d",&number[i]);
}
memset(dp,0,sizeof(dp));
dp[1]=number[1];
for(i=2;i<=N;i++)
{
int start=(i-2)*(i-1)/2+1;
int end=i*(i-1)/2;
for(j=1;j<=i;j++)
{
if(j==1)
{
dp[end+j]=dp[start]+number[end+j];
continue;
}
if(j==i)
{
dp[end+j]=dp[end]+number[end+j];
continue;
}
dp[end+j]=max(dp[start+j-2],dp[start+j-1])+number[end+j];
}
}
int MAX=0;
int start=N*(N-1)/2;
for(i=1;i<=N;i++)
{
MAX=max(MAX,dp[start+i]);
}
printf("%d\n",MAX);
}
return 0;
}
来源:https://www.cnblogs.com/lonelycatcher/archive/2011/05/31/2065137.html