6581 Number Triangle
2023-04-18 12:35:33 时间
6581 Number Triangle
时间限制:500MS 内存限制:1000K
提交次数:57 通过次数:47
题型: 编程题 语言: G++;GCC
Description
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
输入格式
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
输出格式
Your program is to write to standard output. The highest sum is written as an integer.
输入样例
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出样例
30
作者
admin
最原始的数塔问题,,经典的动态规划问题。状态转移方程:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
其他细节见代码注释:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<cctype> 7 #include<algorithm> 8 #include<set> 9 #include<map> 10 #include<vector> 11 #include<queue> 12 #include<stack> 13 #include<utility> 14 #define ll long long 15 #define inf 0x3f3f3f3f 16 using namespace std; 17 18 int a[105][105];//a[i][i]为数塔上点[i][i]处输入的值 19 int dp[105][105];//dp[i][j]为走到点[i][j]所能得的最大值 20 int main() 21 { 22 //freopen("input.txt","r",stdin); 23 memset(a,0,sizeof(a)); //初始化数组 24 memset(dp,0,sizeof(dp)); 25 int n; 26 scanf("%d",&n); //输入数据 27 for(int i=1;i<=n;i++) 28 { 29 for(int j=1;j<=i;j++) 30 { 31 scanf("%d",&a[i][j]); 32 } 33 } 34 // 35 dp[1][1]=a[1][1]; 36 if(n==1) //n为1就直接输入塔顶数字 37 { 38 printf("%d ",dp[1][1]); 39 return 0; 40 } 41 //状态转移方程 42 for(int i=2;i<=n;i++) 43 { 44 for(int j=1;j<=i;j++) 45 { 46 //走到第a[i][j]位置能得到的最大值dp[i][j]就是等于选择从走到a[i-1][j-1]和走到 47 //a[i-1][j]中值较大的那种走法里再加上a[i][j]; 48 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]; 49 } 50 } 51 // 52 int Max=-1; 53 for(int i=1;i<=n;i++)//扫描塔的最下层,找出最大值 54 if(dp[n][i]>Max) 55 Max=dp[n][i]; 56 printf("%d ",Max); 57 return 0; 58 }
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击