[洛谷 1216,poj 1163,codevs 1220][IOI1994]The Triangle

题目链接

https://www.luogu.org/problemnew/show/P1216

http://poj.org/problem?id=1163

http://codevs.cn/problem/1220

大意

数字三角形问题,给出一个数字三角形,求从顶点开始,到达最下面一行的最大路径(每次只能向下方或向右下方走)。

题解

DP中最简单(也是最经典)的一道问题,每次因为只有两种决策(往下方走或者往右下方走),所以状态转移方程很容易可以得出:\(f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j])\),时间复杂度为\(O(n^2)\)。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int n,a[205][205],f[205][205],maxn;
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=i;j++)
   scanf("%d",&a[i][j]);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=i;j++)
   f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);
 for(int i=1;i<=n;i++)
  maxn=max(f[n][i],maxn);
 printf("%d",maxn);
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注