写到一道数位DP的题目，涉及LIS的nlogn解法，拿道LIS模板题复习一下。

  • BUY LOW, BUY LOWER （记录序列数，DP*2）

VJ链接：https://vjudge.net/problem/POJ-1952
//打算把更新放在上面了
对LIS问题有了新认识。。。原来自己以前YY的贪心思想是错的？？nlogn求LIS本质是DP..
dp[len]表示长度为len的上升子序列末端最小值。
比如：
这个题要求最长下降子序列，还有满足这个长度的子序列有多少（去重）。
需要两遍DP。 
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define lowbit(x)  ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,maxlen;
int a[5555];
int dp[5555];//以i结尾的最长下降长度
int cnt[5555];//到i位置的下降序列个数
int main()
{
    while(~s1(n))
    {
        maxlen=0;
        for(int i=1;i<=n;i++) s1(a[i]);
        for(int i=1;i<=n;i++)
        {
            dp[i]=1;
            for(int j=1;j<i;j++)
                if(a[j]>a[i]) dp[i]=max(dp[i],dp[j]+1);
            maxlen=max(maxlen,dp[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for (int j=1;j<i;j++)
                if (a[i] == a[j]) cnt[j] = 0;//去重,将前面的重复的序列的贡献清空
            if (dp[i] == 1) cnt[i] = 1;
            else
            {
                for (int j=1;j<i;++j)
                    if (dp[j]+1 == dp[i] && a[i] < a[j])//如果i可由j转移得到
                        cnt[i] += cnt[j];
            }
        }
        int sum=0;
        for (int i=1;i<=n;++i)
            if (dp[i] == maxlen) sum += cnt[i];
	    printf("%d %d\n",maxlen,sum);
    }
    return 0;
}

  • Bridging signals

VJ链接：https://vjudge.net/problem/HDU-1950
求一个最长递增子序列，通过贪心维护一个d数组，d[len]代表长度为len的子序列末端最小元素
从前向后扫描原数组a并更新d中的各个d[len]值，注释都在代码里啦。 
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi   acos(-1.0)
#define INF   0x3f3f3f3f
#define mod   1000000
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n;
int a[MAXN];//原数组
int d[MAXN];//长度为len的lis末端最小元素//d数组为递增的
int main()
{
    int t;s1(t);
    while(t--)
    {
        s1(n);
        for(int i=0;i<n;i++)
            s1(a[i]);
        d[1]=a[0];
        int len=1;
        for(int i=1;i<n;i++)
        {
            if(a[i]>d[len])
                d[++len]=a[i];
            else
            {
                int pos=lower_bound(d,d+len+1,a[i])-d;
                //这里要找第一个满足d[len]>=a[i]的位置（下界）
                //例如数组2，4，3，4，如果寻找上界
                //扫描到3的时候，d[1]=2,d[2]=4
                //如果寻找上界,找到的是d[1],将d[1]更新为3，显然是不对的
                d[pos]=a[i];
            }
        }
        printf("%d\n",len);
    }
    return 0;
}

  • XHXJ's LIS （数位DP，LIS）

VJ：https://vjudge.net/problem/HDU-4352
看名字很明显啦。。。
条件：一个数满足（看成字符串后）最长递增子序列长度为k
题意：求一段区间内满足条件的数字个数
对于每一个数，要求最长递增子序列，LIS（nlogn）嘛，对于一个区间，数位DP嘛。
模板数位维护数组为：dp[pos][state]，
对于这个题，pos代表到达哪一位，state自然就是此时最长公共子序列情况。
但是对这个题要存一个数组比较困难，所以状压把这个子序列表达为01序列，那么1<<10就可以表达全部状态（或者哈希）
2 3 4就表示为1110（不会出现0123的，0，1，冲突不用管了）。
对于不同的k，再开一维区分不同的k方便记忆话搜索，最后数组就是dp[pos][state][k]。
再复习一下LIS中的贪心思想，，，dfs产生新状态时，维护出一个1.最长2.内部元素字典序最小的子序列。
如果为2545，扫描到4时，发现prestate中为25，此时将5踢出去，维护新状态为24；
如果为234，到4时， prestate为23，新状态234，长度+1；
如果为256345，到3，prestate为256--->state236，
明显此时状态和实际不符，但是长度依然是我们想要的，因为这一步实际在做这个事情
相当于开了一串新序列）
把后面情况一块画出来了丑就丑啦.......）
扫描到后面5的时候就应该知道为什么在这么贪心了。
另外就是找第一个>=x的值进行替换。上一个题强调过了。
//咦写这个题是想练数位DP来着，，好像只有LIS部分想写一写。

	#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi   acos(-1.0)
#define INF   0x3f3f3f3f
#define mod   1000000
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)





	int k;
ll l,r;
int a[30];
ll dp[30][1<<11][11];
//dp[pos][prestate][k]
//到达pos处，前一个状态为prestate,此位置数字取0~9满足限定条件的数字数目和
int getnum(int s)
{
    int num=0;
    while(s)
    {
        num+=(s&1);s>>=1;
    }
    return num;
}
int getnew(int s,int x)
{
    for(int i=x;i<10;i++)
    {
        if(s&(1<<i))
        {
            s^=(1<<i);
            break;
        }
    }
    return s|(1<<x);
}
ll dfs(int pos,int prest,int limit,int zero)
{
    if(pos==-1) return (getnum(prest)==k);
    if(!limit&&dp[pos][prest][k]!=-1) return dp[pos][prest][k];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++)
        ans+=dfs(pos-1,zero&&i==0?0:getnew(prest,i),limit&&i==up,zero&&i==0);
    if(!limit) dp[pos][prest][k]=ans;
    return ans;
}
ll solve(ll x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,1,1);
}
int main()
{
    int t;s1(t);
    int tt=1;
    mem(dp,-1);
    while(t--)
    {
        scanf("%lld %lld %d",&l,&r,&k);
        if(l==r)
            printf("Case #%d: 0\n",tt++);
        else
            printf("Case #%d: %lld\n",tt++,solve(r)-solve(l-1));
    }
    return 0;
}