USACO Section1.5 Number Triangles 解题报告
numtri解题报告 —— icedream61 博客园(转载请注明出处)
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
有一个数字的金字塔,形状如下
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
要从顶端开始走,每次只能向左下或者右下走,求所经过的数字之和最大值。
【数据范围】
1<=R<=1000
0<=每个数<=100
【输入样例】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【输出样例】
30
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
DP。
设num[i][j]为i行j列的数,d[i][j]是从1行1列走到i行j列的当前最优解。
d[1][1]=num[1][1];
d[i][j]=0; // i>1 or j>1
从1行1列走到R行某列的最大值,可以直接递归出来,状态转移方程如下:
当i==1,j>=2时,d[i][j]=d[i-1][j]+num[i][j];
当i>=2,j>=2时,d[i][j]=max{d[i-1][j]+num[i][j],d[i-1][j-1]+num[i][j]};
但本题,递归有边界情况,比较麻烦,递推更方便,状态转移方程如下:
当i>=2,2<=j<R时
d[i+1][j]=max{d[i+1][j],d[i][j]+num[i+1][j]};
d[i+1][j+1]=max{d[i+1][j+1],d[i][j]+num[i+1][j+1]};
最终,只要扫过d[R][1~R]取得最大值输出即可。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
一遍AC。
------------------------------------------------------------------------------------------------------------------------------------------------
【代码】
/*
ID: icedrea1
PROB: numtri
LANG: C++
*/ #include <iostream>
#include <fstream>
using namespace std; int R;
int num[][],d[][]; void change(int &r,int x) { if(x>r) r=x; } int main()
{
ifstream in("numtri.in");
ofstream out("numtri.out"); in>>R;
for(int i=;i<=R;++i)
for(int j=;j<=i;++j) in>>num[i][j]; d[][]=num[][];
for(int i=;i<R;++i)
for(int j=;j<=i;++j)
{
change(d[i+][j],d[i][j]+num[i+][j]);
change(d[i+][j+],d[i][j]+num[i+][j+]);
} int maxSum=;
for(int j=;j<=R;++j) change(maxSum,d[R][j]);
out<<maxSum<<endl; in.close();
out.close();
return ;
}
最新文章
- php中会话保持 session 与cooker
- function中的ajax怎么返回一个数
- ZJOI2014 2048
- hdu4825 字典树 XOR
- insert into hi_user_score set hello_id=74372073,a=10001 on duplicate key update hello_id=74372073, a=10001
- 【服务器环境搭建-Centos】tmpfs,【转载】
- Java程序发展之路
- C语言格式化输出,空位补0,空位补空格
- 使用Android简单实现有道电子词典
- HOJ2275 Number sequence
- hdu_5711_Ingress(TSP+贪心)
- vue视频学习笔记07
- 怎么用VBS脚本自动注册yy娱乐的账号
- AIO5程序中审批跳转条件:超过某一个值必须总经理审批
- android 滑动分页
- 在 Ubuntu 系统中部署 Git Server
- 查看ntp时间是否同步
- MySQL报错: SQLSTATE[HY000]: General error: 1030 Got error 28 from storage engine
- java实现文件的断点续传
- vue全局变量定义和修改