RT

题目描述

数字三角形必须经过某一个点，使之走的路程和最大

输入

第1行n，表示n行 <=25

第2到n+1行为每个的权值

程序必须经过n / 2,n / 2这个点

输出

最大值

样例输入

2

1

1 1

样例输出

2

wa code

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N][N],f[N][N],n,ans,tot[N][N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)
		cin>>a[i][j];
	f[1][1]=a[1][1];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)
	{
		f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
		if((i==n/2 && j==n/2) || tot[i-1][j-1]==1 || tot[i-1][j]==1)
		tot[i][j]=1;
	}
    for(int i=1;i<=n;i++)
    {
    	if(tot[n][i]==1)
    	ans=max(ans,f[n][i]);
	}
    cout<<ans;
	return 0;
}

最近发dp的帖子有点多，大佬们多多包容