Codevs 数字三角形 问题合集
2024-09-25 15:53:16
1220 数字三角形
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold
题目描述 Description
如图所示的数字三角形,从顶部出发,在每一结点可以选择向左走或得向右走,一直走到底层,要求找出一条路径,使路径上的值最大。
输入描述 Input Description
第一行是数塔层数N(1<=N<=100)。
第二行起,按数塔图形,有一个或多个的整数,表示该层节点的值,共有N行。
输出描述 Output Description
输出最大值。
样例输入 Sample Input
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
样例输出 Sample Output
86
数据范围及提示 Data Size & Hint
数字三角形
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int w[][],n;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
scanf("%d",&w[i][j]);
for(int i=n-;i>=;i--)
for(int j=;j<=i;j++)
w[i][j]+=max(w[i+][j],w[i+][j+]);
printf("%d",w[][]);
return ;
}
2189 数字三角形W
时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold
题目描述 Description
数字三角形
要求走到最后mod 100最大
输入描述 Input Description
第1行n,表示n行
第2到n+1行为每个的权值
输出描述 Output Description
mod 100最大值
样例输入 Sample Input
2
1
99 98
样例输出 Sample Output
99
数据范围及提示 Data Size & Hint
n<=25
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int p=;
int w[][],n,f[][][];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
scanf("%d",&w[i][j]);
f[][][ ((w[][]%p) + p)%p ]=; for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
for(int k=;k<=;k++)
f[i][j][k]=f[i-][j][( ( k-w[i][j]) %p+p ) %p ]||
f[i-][j-][( ( k-w[i][j]) %p+p ) %p ];
int maxx=;
for(int i=;i<=n;i++)
for(int j=;j>=;j--)
if(f[n][i][j]) maxx=max(maxx,j);
printf("%d",maxx);
return ;
}
说实话这道题我不知道是不是动态规划,这DP也不是我写的(可能是数据太水把我放过去了),我觉得这不满足动态规划无后效性的原则,望大神路过留言。。。
2193 数字三角形WW
时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond
题目描述 Description
数字三角形必须经过某一个点,使之走的路程和最大
输入描述 Input Description
第1行n,表示n行
第2到n+1行为每个的权值
程序必须经过n div 2,n div 2这个点
输出描述 Output Description
最大值
样例输入 Sample Input
2
1
1 1
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
n <=25
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,x,y,w[][],ko;
long long f[][];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
scanf("%d",&w[i][j]);
f[][]=w[][];
w[n/][n/]+=;
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
f[i][j]=w[i][j]+max(f[i-][j],f[i-][j-]);
long long ans=;
for(int i=;i<=n;i++)
ans=max(ans,f[n][i]);
printf("%lld",ans-);
return ;
}
这次是正推。。
2198 数字三角形WWW
时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond
题目描述 Description
数字三角形必须经过某一个点,使之走的路程和最大
输入描述 Input Description
第1行n,表示n行
第2到n+1行为每个的权值
第n+2行为两个数x,y表示必须经过的点
输出描述 Output Description
最大值
样例输入 Sample Input
2
1
1 1
1 1
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
n<=25
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,x,y,w[][],ko;
long long f[][];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
scanf("%d",&w[i][j]);
scanf("%d%d",&x,&y);
w[x][y]+=;
f[][]=w[][];
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
f[i][j]=w[i][j]+max(f[i-][j],f[i-][j-]);
long long ans=;
for(int i=;i<=n;i++)
ans=max(ans,f[n][i]);
printf("%lld",ans-);
return ;
}
最新文章
- 如何装最多的水? — leetcode 11. Container With Most Water
- 2016年11月7日 星期一 --出埃及记 Exodus 19:23
- 第五篇、常用的SQL语句和函数介绍
- js获得url的参数
- Centos 5.5 更新网卡驱动 bnx2 version: 2.0.2
- oracle12c(oracle12.1.0.1.0)安装指南--实测OEL5.9(RH5)
- delphi学习treeview中从表列名和数据添加为目录并双击自动选中
- HDU1969:Pie(二分)
- .net core 同时实现网站管理员后台、会员、WebApi登录及权限控制
- 关于SQL性能优化的十条经验
- 【Android Studio安装部署系列】二十九、Android Studio安装本地插件(以国际化方法插件AndroidLocalizationer为例)
- [Swift]LeetCode952. 按公因数计算最大组件大小 | Largest Component Size by Common Factor
- 【转】10 个很有用的 jQuery 弹出层提示插件
- Linux系统下DNS主从配置详解
- 一个随机验证码且不重复的小程序以及求随机输入一组数组中的最大值(Java)
- python MySQL慢查询监控
- postgresql 匿名函数(单独执行代码段)
- Java数据类型和不同数据类型在JVM内存分配
- canvas 绘制双线技巧
- 关于JAVA多线程并发synchronized的测试与合理使用