The Triangle POJ - 1163 (dp水题)
dp基础的不能再基础的题
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const LL maxn = 110;
int n, t[maxn][maxn], dp[maxn][maxn];
int solve()
{
ms(dp, 0);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + t[i][j];
int ans = -1;
for(int i = 1; i <= n; i++)
if(dp[n][i] > ans) ans = dp[n][i];
return ans;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> t[i][j];
cout << solve() << endl;
return 0;
}