Home > Old Blog Posts > USACO 1.5.1 Number Triangles

USACO 1.5.1 Number Triangles


DP的入门题,从上往下或从下往上推都可以,我用的是从下往上推

f[i][j]代表取到第i行第j个数时所能取到的最大值,则

f[i][j]=max(f[i+1][j],f[i+1][j+1])

优化:pascal用滚动数组,C++用指针可以将存储空间从O(n^2)降到O(n)。

代码:

/*
ID: dementr1
PROG: numtri
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“numtri.in”);
ofstream fout(“numtri.out”);
int a[1001][1001];
int main()
{
int n,i,j;
fin>>n;
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
fin>>a[i][j];
for(i=n-2;i>=1;i–)
for(j=i;j>=0;j–)
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
fout<<a[0][0]+max(a[1][0],a[1][1])<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: