HDU 4352 XHXJ's LIS HDU(数位DP)
2024-10-09 06:09:35
HDU 4352 XHXJ's LIS HDU
题目大意
给你L到R区间,和一个数字K,然后让你求L到R区间之内满足最长上升子序列长度为K的数字有多少个
solution
简洁明了的题意总是让人无从下手
数字——数位DP
根据题意定义数组
第一维:数位
第二维:数位状态01串
第三维:个数K的大小
说说心路历程:
写的时候没有注意到前导零的可能型(通过看大佬的blog发现的
问题就是如何进行状态转移(手动@LC参考了LC的题解
我们用一个长度为10的二进制数表示数字几有没有被选到
如果为0,则表明该位对应的数字是最长上升子序列的一部分,反之则不是
每次遍历时,如果新加入的数是最大的,我们就直接把该数代表的位置置为1就可以
如果新加入的数不是最大的,我们就把第一个小于等于该位的数置为0,把新加入的位数置为1
统计长度时只要看有几个1就可以了
题解看懂了,code未完成
最新文章
- WinForm构造函数的作用
- apache启动出错原因举例
- 【BZOJ-2251】外星联络 后缀数组 + 暴力
- linux 用户、用户组不能是全数字
- Toad快速入门
- centos7.0 手动编译 lamp环境
- java常用包
- iOS开发之多媒体API
- UGUI 锚点
- C# 队列数据结构 (三)
- C# 4.0 新特性-dynamic 【转】
- JSP动态网站环境搭建应用中的详细步骤(Tomcat和Apache/IIS的整合)
- C#中运算符的应用
- word中表格第一列序号的设置
- LeetCode第四天
- Python之旅.第三章.函数3.26
- Python读取文件时输入文件绝对路径报错
- OpenResty的现状、趋势、使用及学习方法
- MAC 下 Excel打开UTF-8格式的文件乱码
- iOS - 开发中加载本地word/pdf文档说明