三角形xjoi 8.14
2024-10-20 16:05:52
问题描述:
离圣诞节只有一个月了,家里要你准备一个很大的星星,然后把它粘在圣诞树的顶端。你已经准备好了一个三角形的银色包装纸来做星星,可忽然有一天你发现在这张大纸上被弄了好多的小洞,原来是你的弟弟妹妹已经从这张大纸上剪掉了许多小的三角形,做了很多小星星。现在,你只能将就了,看怎样才能从这残缺的大纸中,找出一块最大的完整的三角形。
如下图所示,假设给你一张大的三角形纸,里面黑的三角形是被你的弟弟妹妹剪掉了的,需要你在剩下的白色区域中找出一个最大的三角形区域。
问题求解:
你现在要找出这样一个算法,并用程序实现它。
输入格式:
输入文件包括几组关于大三角形样子的描述。输入每一组的第一行是一个整数N(1≤N≤100)表示下面要描述的大三角形的高度。接下来的N行将用许多字符模拟出大三角形的样子,其中用“X”表示被剪掉的小三角形(即上图中的黑三角形),用“O”表示 白色区域。每行字符个数从(2N-1)到1递减。如果组首为0,则表示结束。
输出格式:
对于输入中的每一个三角形,输出一个数,表示剩下部分所能得到的最大的三角形的面积,而该数就是其中所包含的小三角形的个数。输出格式如样例,如第2组数据,最大面积为4,则输出:
Triangle #2
The largest triangle area is 4
样例输入:
5
XOXXOOOOX
OOOOOXO
OOOXO
OXO
O
4
XOXOXOO
XOOOX
XXO
O
0
样例输出:
Triangle #1
The largest triangle area is 9
Triangle #2
The largest triangle area is 4
数据范围:
0≤N≤100
数据组数据<=100
题解:这题刚开始是真的想不到,只知道是个DP但不知道状态怎么转移,因为我想的是三角形不断变大,最上面一行的三角形就
不断增加,这要我怎么记录?
最后看了一下题解才豁然省悟,每个三角形f[i,j]只和f[i-1,j],f[i-1,j-1],f[i,j-2]有关!每个大三角形中都有许多这样的小三角形(4个组成)
dp方程就是if a[i-1,j-1]是不是白色,那么f[i,j]=min(f[i-1,j],f[i-1,j-2])+1。(最小的那个才连的起来)不需要f[i-1,j],f[i,j-2]是否是白色区域,刚开始预处理白色为1,黑色为0。因为正倒三角形都有可能,所以正反都搜一次。f[i,j]:=min(f[i+1,j],f[i+1,j+2])+1.
代码就不贴啦。
最新文章
- 探索c#之尾递归编译器优化
- CSS调试小技巧 —— 调试DOM元素hover,focus,actived的样式
- python Tornado(招聘的一个比较经常问到的知识)
- PHP, LDAPS and Apache
- BroadcastReceiver之SD的挂载监听
- Android开发者必备的42个链接
- 吐个槽,对VB6.0 还有VBS 说ByeBye
- 封装getByClass
- 看完这些,你就算得上既了解围棋又了解alphago了
- JS点击任意标签获得该标签属性,以获得ID为例,以及AJAX的异步原理和 $(document).ready()与window.onload加载方法的区别
- mysql修改root密码的方法
- PHP批量去除bom头代码的小工具
- js时间国际化
- Android Studio--按钮跳转新页
- 如何通过钉钉扫码登录odoo
- 《剑指offer》第六十一题(扑克牌的顺子)
- 20155208实验三 敏捷开发与XP实践
- 在VMware上安装Ubuntu软件步骤与遇到的相关问题及解决方案
- 生命周期事件和 Global.asax 文件
- docker中实现服务日志轮转
热门文章
- day1 python 介绍、基本语法、流程控制
- (EXPDP) Fails With Errors ORA-39079 ORA-25306 On One Node In RAC Environment
- 字段处理rtrim去掉结尾的特殊字符和空格
- Django Request 与Response对象
- (转)Wireshark基本介绍和学习TCP三次握手
- 【洛谷5280】[ZJOI2019] 线段树(线段树大力分类讨论)
- XCode插件因为升级不能用了怎么办?几个步骤教你搞定
- VS Code 中 HTML 文档注释 js 语句异常
- EF6 AddOrUpdate之后,数据没有改变而是新增了一条数据解决办法
- SpringBoot非官方教程 | 第四篇:SpringBoot 整合JPA