hdu4352-XHXJ's LIS状压DP+数位DP
2024-08-30 21:17:46
(有任何问题欢迎留言或私聊 && 欢迎交流讨论哦
题意:传送门
原题目描述在最下面。
在区间内把整数看成一个阿拉伯数字的集合,此集合中最长严格上升子序列的长度为k的个数。
思路:
看了大神的博客感觉这东西是真难想到。状压dp预处理状态,数位dp计算答案。
nex[i][j]
表示在状态i(状态i的二进制中为1表示这个数存在LIS中,反之不存在),选取加入第j的数字之后的状态。
然后这题k最大也只有10,因为只有10个数字。所以状态只有1024种。这题还要处理一下前导0。
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int mod = 1e9;
const int N = (int)1e2+7;
LL n, m, k;
int one[1<<10], ar[30], nex[1<<10][10];
LL dp[30][1<<10][11];
int get(int x, int y){
for(int i = y; i < 10; ++i){
if(x&(1<<i)) return (x^(1<<i))|(1<<y);
}
return x|(1<<y);
}
void init(){
for(int i = 0; i < (1<<10); ++i){
for(int j = 0; j < 10; ++j){
if(i&(1<<j))one[i]++;
nex[i][j] = get(i, j);
}
}
memset(dp,-1,sizeof(dp));
}
LL dfs(int pos, int sta, bool lead, bool limit){
if(pos == -1)return one[sta] == k;
if(!limit&&!lead&&dp[pos][sta][k] != -1) return dp[pos][sta][k];
int up = limit? ar[pos]: 9;
LL sum = 0;
for(int i = 0; i <= up; ++i){
sum +=dfs(pos-1,(lead&&i==0)?0:nex[sta][i],lead&i==0,limit&&i==ar[pos]);
}
if(!limit&&!lead)dp[pos][sta][k] = sum;
return sum;
}
LL solve(LL x){
int pos = 0;
while(x){ar[pos++]=x%10;x/=10;}
return dfs(pos-1,0,1,1);
}
int main(){
init();
int tim,tca=0;
scanf("%d", &tim);
while(tim--){
scanf("%lld%lld%lld", &n, &m, &k);
printf("Case #%d: %lld\n", ++tca, solve(m)-solve(n-1));
}
return 0;
}
####原题目描述:
![这里写图片描述](https://img-blog.csdn.net/20180722103729350?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTk5MDY3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)
最新文章
- Eclipse不能自动编译 java文件
- XP退役了,如何把Win7变成XP风格?| 怎么样去掉Win7的所有华丽效果? | 怎么样让Win7达到电脑最佳性能?
- Docker与容器快速入门
- 解决li在ie,firefox中行高不一致问题
- POJ-3140 Contestants Division (树)
- shell之here文档
- c语言解数独
- hdu 4722 Good Numbers(规律题)
- IIS网站部署错误总结
- 关于 wait_event_interruptible() 和 wake_up()的使用
- uva103(最长递增序列,dag上的最长路)
- 关于UI_USER_INTERFACE_IDIOM() &; UIDevice.model
- ubuntu下如何安装和卸载wine-qq
- hello 内核模块
- .NET Core + Ocelot + IdentityServer4 + Consul 基础架构实现
- Python_自定义递归的最大深度
- Java多线程:SimpleDateFormat
- 浅析vue的双向数据绑定
- LG4196 [CQOI2006]凸多边形
- 20155327 实验四 Android程序设计
热门文章
- vmware下搭建openwrt
- C/C++ volatile
- 深入浅出 Vue.js 第九章 解析器---学习笔记
- nodejs 内存泄漏
- Java-Class-C:com.ylbtech.api.platfrom.util.RedisUtils.class
- 框架-.NET:Spring.Net
- sea.js模块加载工具
- Linux文件映射的反思
- DLL 调用 对话框 以及 如何获取调用dll 应用程序(窗口程序)的窗口句柄
- wordpress 上传图片时提示“无法建立目录wp-content/uploads/2019/03。有没有上级目录的写权限?”