TIOJ 1288 D.三角旅行

[DP]

#include<stdio.h>
#include<string.h>
#define max(a,b) (((a)>(b)) ? (a):(b))
int main()
{
    int TB[102][102];
    int OT[102][102];
    int N;
    memset(TB,0,sizeof(TB));
    memset(OT,0,sizeof(OT));
    scanf("%d",&N);
    for(int lx=1;lx<=N;lx++)
        for(int ly=1;ly<=lx;ly++)
            scanf("%d",&TB[lx][ly]);
    OT[1][1]=TB[1][1];
    for(int lx=2;lx<=N;lx++)
        for(int ly=1;ly<=lx;ly++)
            OT[lx][ly]=max(OT[lx-1][ly-1],OT[lx-1][ly])+TB[lx][ly];
    int m=0;
    for(int lx=1;lx<=N;lx++)
        m=max(m,OT[N][lx]);
    printf("%d\n",m);
    return 0;
}