1 //Accepted    220 KB    0 ms 2 //dp 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 105; 8 int map[imax_n][imax_n]; 9 int dp[imax_n][imax_n];10 int n;11 int max(int a,int b)12 {13     return a>b?a:b;14 }15 void Dp()16 {17     memset(dp,0,sizeof(dp));18     for (int i=1;i<=n;i++)19     {20         for (int j=1;j<=i;j++)21         dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+map[i][j];22     }23     int ans=0;24     for (int i=1;i<=n;i++)25     ans=max(ans,dp[n][i]);26     printf("%d\n",ans);27 }28 int main()29 {30     while (scanf("%d",&n)!=EOF)31     {32         memset(map,0,sizeof(map));33         for (int i=1;i<=n;i++)34         {35             for (int j=1;j<=i;j++)36             scanf("%d",&map[i][j]);37         }38         Dp();39     }40     return 0;41 }