//1163 an easy dp problem 
#include <stdio.h>
struct num
{
	int val;
	int sum;
}org[100][100];
void input(int t)
{
	int tp1;int tp2;
	for(tp1=1;tp1<=t;tp1++)
	{
		for(tp2=0;tp2<tp1;tp2++)
		{
			scanf("%d",&org[tp1-1][tp2].val);
		}
	}
}

void clr()
{
	int a;
	for(a=0;a<10000;a++)
	{
		org[a/100][a%100].val =-1;
		org[a/100][a%100].sum =-1;
	}
}

int max(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}

int cal(int c,int d,int t)
{
	if(org[c][d].sum =-1)
	{
		if(c<t-1)
			org[c][d].sum =max(cal(c+1,d,t),cal(c+1,d+1,t))+org[c][d].val;
		if(c==t-1)
			org[c][d].sum =org[c][d].val;
	}
	return org[c][d].sum;
}

void output(int ans)
{
	printf("%d\n",ans);
}

void work(int t)
{
	int ans;
	input(t);
	ans=cal(0,0,t);
	output(ans);
}

int main()
{
	int t;
	while(scanf("%d",&t)!=EOF)
	{
		clr();
		work(t);
	}
	return 0;
}

• cal()里有个地方==-1写成=-1了... (1049) MrRight 2006-12-09 00:24:12
  • oh my god ... 谢谢指教,(虽然从TLE 变成了 WA) (0) FOR_RITZ 2006-12-09 00:25:59
    • 晕,调教的时候改了另外 一个地方忘记改回来了,谢谢了。看来暴露自己很多习惯没养成。 (0) FOR_RITZ 2006-12-09 00:29:34
• Re:用DP做了,可是TLE? 本人DP写的不怎么好,请望指教。 (11) 20053565 2006-12-14 11:51:21