2189 数字三角形W

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

分类标签 Tags 点此展开

最后一维记录这个数%p可不可能到达

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=26;
 6 int n;
 7 int a[MAXN][MAXN];
 8 bool f[MAXN][MAXN][101];
 9 int main()
10 {
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++)
13         for(int j=1;j<=i;j++)
14             cin>>a[i][j];
15     
16     for(int i=1;i<=n;i++)f[n][i][a[n][i]%100]=1;
17     
18     for(int i=n-1;i>=1;i--)
19         for(int j=1;j<=i;j++)
20             for(int k=0;k<=99;k++)
21             f[i][j][k]=f[i+1][j][(k-a[i][j]+100)%100]||f[i+1][j+1][(k-a[i][j]+100)%100];
22     
23     for(int k=100;k>=1;k--)
24         if(f[1][1][k]==1){cout<<k;break;}
25     return 0;
26 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

Java--多态性之抽象类和接口

1764
来自专栏拭心的安卓进阶之路

深入理解 Java 反射:Method (成员方法)

深入理解 Java 反射系列: 深入理解 Java 反射:Class (反射的入口) 深入理解 Java 反射:Field (成员变量) 深入理解 Java ...

3977
来自专栏数据结构与算法

1081 线段树练习 2 单点查询及区间修改

1081 线段树练习 2 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 Description ...

3279
来自专栏一个会写诗的程序员的博客

《Kotlin 极简教程 》第6章 泛型

通常情况的类和函数,我们只需要使用具体的类型即可:要么是基本类型,要么是自定义的类。

1253
来自专栏落影的专栏

Swift学习笔记

这是一篇学习swift的笔记 Objective-C是很好的语言,Runtime机制、消息机制等也是爱不释手。 Swift一直在更新,闲暇时间学一遍。学习的B...

4427
来自专栏于晓飞的专栏

Java 泛型进阶

在 List<String> 中添加 Integer 将不会通过编译,但是List<Sring>与List<Integer>在运行时的确是同一种类型。

2193
来自专栏每日一篇技术文章

Swift3.0 - 类和结构体的区别

结论: 在数据量比较大的排序中,结构体排序的速度比较慢,因为结构体是值类型,排序的时候,需要大量的赋值运算。而对象只需要交换地址即可。

1031
来自专栏Java帮帮-微信公众号-技术文章全总结

05-02总结方法,数组(一维)

/* 练习题(1) 数组遍历:就是依次输出数组中的每一个元素。 注意:数组提供了一个属性length,用于获取数组的长度。 格式:数组名.lengt...

3597
来自专栏每日一篇技术文章

Foundation-String

最近写完了Swift 3.0教程 ,在接下来这段时间,继续写Foundation 的教程,帮助大家更加深入,系统的学习Foundation 框架,可能会持续一段...

1091
来自专栏彭湖湾的编程世界

【算法】实现栈和队列

栈(stack) 栈(stack)是一种后进先出(LIFO)的集合类型, 即后来添加的数据会先被删除 ? 可以将其类比于下面文件的取放操作:新到的文件会被先取走...

3456

扫码关注云+社区

领取腾讯云代金券