HDU4352 XHXJ's LIS(LIS 状压)

题意

题目链接

Sol

刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

题解,,,挺暴力的把,直接把求LIS过程中的单调栈当成一个状态压进去了。。

自己真是不长记性,明明已经被这个单调栈坑过一次了。。

考虑到$k$非常小,于是直接对$k$进行状压

设$f[i][sta][j]$表示长度为$i$,单调栈内状态为$sta$, LIS长度为$k$的方案数

最后一维如果是单组数据的话是不必要的。但是考虑到时多组数据,就一起加进来吧。

转移的时候枚举一下这一位放了什么,然后暴力的改一下LIS的状态。

#include<bits/stdc++.h>
#define LL long long 
#define int long long 
using namespace std;
const int MAXN = 1e5 + 10;
LL T, l, r, K;
int f[64][1 << 10][11];//长度为i,lis为k的方案数
int a[MAXN], num;
int change(int S, int x) {//向状态s中加入一个数x
    for(int i = x; i <= 9; i++)
        if(S & (1 << i)) {S ^= (1 << i); break;} 
    return S | (1 << x);
}
int dfs(int now, int lim, int lead, int s) {
//  printf("%d %d %d %d\n", now, lim, lead, s);
    if(!now) return (__builtin_popcount(s) == K);
    if(!lim && f[now][s][K] != -1) return f[now][s][K];
    int ans = 0;
    for(int i = 0; i <= (lim ? a[now] : 9); i++) 
        ans += dfs(now - 1, lim && i == a[now], lead && (!i), (lead && (!i)) ? 0 : change(s, i));
    if(!lim) f[now][s][K] = ans;
    return ans;
}
LL solve(LL x) {
    num = 0;
    while(x) a[++num] = x % 10, x /= 10;
//  cout << num << endl;
    dfs(num, 1, 1, 0);
}
 main() {
    memset(f, -1, sizeof(f));
    cin >> T;
    for(int i = 1; i <= T; i++) {
        cin >> l >> r >> K;
        printf("Case #%d: ", i);
        cout << solve(r) - solve(l - 1) << endl;
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据科学学习手札

(数据科学学习手札06)Python在数据框操作上的总结(初级篇)

数据框(Dataframe)作为一种十分标准的数据结构,是数据分析中最常用的数据结构,在Python和R中各有对数据框的不同定义和操作。 Python 本文涉及...

6675
来自专栏灯塔大数据

每周学点大数据 | No.5算法的分析之图灵机

No.5期 算法的分析之图灵机 小可:那计算机科学有没有对易解和难解问题进行一个相对严格的界定呢? Mr. 王:有的,这里既然提到了多项式算法和易解难解问题,...

3748
来自专栏聊聊技术

原 "二分查找(Binary Search

42911
来自专栏苦逼的码农

【算法实战】生成窗口最大值数组

做算法题了,题的难度我们分为“士,尉,校,将”四个等级。这个算法题的模块是篇幅比较小的那种模块。首先是给出一道题的描述,之后我会用我的想法来做这道题,今天算是算...

1172
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

922
来自专栏WD学习记录

数据结构与算法2016-06-01

1.数据结构包括数据的逻辑结构和物理结构。数据的逻辑结构就是从具体问题抽象出来的数学模型,是为了讨论问题的方便,与数据在计算机中的具体存储没有关系。讨论数据结构...

922
来自专栏潇涧技术专栏

Python Algorithms - C2 The basics

本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

1052
来自专栏码匠的流水账

聊聊leaky bucket算法的实现

1291
来自专栏编程之旅

数据结构——最短路径Dijkstra算法

在上一篇博文里,我记录了最小生成树的算法实现,而在这篇里,我们来讲讲查找最短路径的算法,Dijkstra算法。

1812
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程1

前言 这里是一篇新手教程,环境是Xcode7+OpenGL ES 2.0,目标写一个OpenGL ES的hello world。 OpenGL ES系列教程在...

3309

扫码关注云+社区

领取腾讯云代金券