[USACO 2009 Nov B]Cow Pinball

Here's an example triangle and a good route: 7 *7 3 8 *3 8 8 1 0 *8 1 0 2 7 4 4 2 *7 4 4 4 5 2 6 5 4 *5 2 6 5 In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30. It's not possible to go from 7 to 8 to 8 -- the 8 on the third row is too far away.

pypy3(pypy3.6.1) 解法, 执行用时: 40ms, 内存消耗: 18740K, 提交时间: 2021-05-03 22:09:13

n=int(input())
a=[]
for i in range(n):
        b=[int(i) for i in input().split()]
        a.append( b)
dp=[[0]*n]*n
for i in range(n):
    dp[n-1][i]=a[n-1][i]
for i in range(n-2,-1,-1):
    for j in range(i+1):
        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]
print(dp[0][0])

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2019-09-17 16:05:11

#include<iostream>
using namespace std;
int main()
{
	int n,r[30][30];
	cin>>n;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			scanf("%d",&r[i][j]);
		}
	}
	for(int i=n;i>1;--i){
		for(int j=1;j<n;++j){
			r[i-1][j]+=max(r[i][j],r[i][j+1]);
		}
	}
	cout<<r[1][1];
	return 0;
}

C++(clang++11) 解法, 执行用时: 12ms, 内存消耗: 516K, 提交时间: 2021-05-03 23:00:47

#include<iostream>
#include<cstdio>
using namespace std;
int n,ans,s,a[1010];
int main()
{
	cin>>n;
	for(int i=n;i>=1;i--)
	for(int j=i;j<=n;j++)
	{
		cin>>s;
		a[j]=max(a[j],a[j+1])+s; 
	}
	for(int i=1;i<=n;i++)
	ans=max(ans,a[i]);
	cout<<ans;
}

Python3 解法, 执行用时: 42ms, 内存消耗: 4564K, 提交时间: 2023-05-02 16:14:38

n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
for i in range(n-2, -1, -1):
    for j in range(i+1):
        x[i][j] += max(x[i+1][j], x[i+1][j+1])
print(x[0][0])

详情