数学三角 动态规划

解题思路:利用结构体变量为二维数组来存储变化的数据与左右移动的次数 

|r-l|>=1   r+l=N    所以 r与l   都<=(N+1)/2

注意事项:

参考代码:

#include<stdio.h>

#include<string.h>

#include<math.h>

#define Max(x,y) (x>y)?x:y

struct node

{

int data;

int r;

int l;

}t[101][101];

int main()

{

int N;

scanf("%d",&N);

int t1,t2;

memset(t,0,sizeof(t));

for(t1=1;t1<=N;t1++)

for(t2=1;t2<=t1;t2++)

scanf("%d",&t[t1][t2].data);

for(t1=1;t1<=N;t1++)

for(t2=1;t2<=t1;t2++)

{

if(t[t1-1][t2-1].data<t[t1-1][t2].data)

{

t[t1][t2].l=t[t1-1][t2].l;

t[t1][t2].r=t[t1-1][t2].r;

t[t1][t2].l++;

}

if(t[t1-1][t2-1].data>t[t1-1][t2].data)

{

t[t1][t2].l=t[t1-1][t2-1].l;

t[t1][t2].r=t[t1-1][t2-1].r;

t[t1][t2].r++;

}

if(t[t1][t2].l<=(N+1)/2 && t[t1][t2].r<=(N+1)/2)

{ t[t1][t2].data=Max(t[t1-1][t2].data+t[t1][t2].data,t[t1-1][t2-1].data+t[t1][t2].data);

}

}

if(N%2==1)

printf("%d\n",t[N][N/2+1].data);

else

printf("%d\n",Max(t[N][N/2].data,t[N][N/2+1].data));

return 0;

}