钟金泽 @ 2017-07-18 20:27:43
#include <iostream>
using namespace std;
int a[2000][1024];
int f[2000][1024];
int n;
long ans;
void dfs(int x, int y, int val)
{
val += a[x][y];
// 记忆化过程
if(val <= f[x][y]) return;
f[x][y] = val;
if(x == n-1)
{
if(val > ans) ans = val;
return;
}
dfs(x+1, y, val);
dfs(x+1, y+1, val);
}
int main()
{
int i,j;
// freopen("ceshi.in","r",stdin);
cin >> n;
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
cin >> a[i][j];
dfs(0,0,0);
cout << ans;
return 0;
}
by 「已注销」 @ 2017-08-06 19:48:20
#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],r;
int main(){
cin>>r;
for(int i=1;i<=r;i++){
for(int j=1;j<=i;j++)cin>>a[i][j];
}
for(int i=r;i>1;i--){
for(int j=1;j<i;j++)a[i-1][j]+=max(a[i][j],a[i][j+1]);
}
cout<<a[1][1];
}