XHXJ's LIS HDU - 4352 数位dp

参考博客:https://www.cnblogs.com/ZGQblogs/p/10679934.html

//dp[pos][sta][k]
//搜索到第几位,之前的最长上升子序列的状态,就是输入的那个k
//sta的二进制每一位,都对应了数位上的一个数字
//举例来说:如果sta按照数字13425来更新。
//首先遇到1,变成0100000000(或者0000000010,其实这是完全一样的,只要保证不同状态的sta不一样就行了)
//然后遇到3,很明显,之前没有比3更大的数字,然后变成0101000000
//遇到4,sta变成0101100000
//不难看出,sta中1的个数,就是LIS的长度
//然后遇到2,这时大于等于2的有一个3.于是把3的二进制1交给2,sta变成0110100000
//为什么这么做?????
//首先我们知道,这样做绝不会改变1的个数,如果之前出现过2
//那么sta就不会变化,否则就把之后最近的那个1挪到当前位置
//然后再看这4个数字:1342
//如果之后出现的数字有比这四个数字都大的,那么之前究竟是1243还是1342都对后方的更新没有影响了
//就如同例子中的5,它只需知道,在之前出现的数字中最大的没有自己大就行了,因为只要这样,就可把5位置的0变成1
//注意:如果有多种状态,( 1243 ,1342 ),只要对后续影响相同,就可以看做同一种状态
//如果之后出现的数字没有比这四个数都大的,那么还是不会改变1的个数
//但是,出现数字2的时候,第二个1向前挪了一位,这实际上是把LIS为2的序列由13变成了12,这里对后续的影响是不同的
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int digit[30];
ll dp[30][1<<10][12];
int Update(int state,int bit){
    for(int i = bit; i <= 9; i++){
        if(state & (1 << i)){
            state ^= (1 << i);
            break;
        }
    }
    return state | (1 << bit);
}
int Getlen(int state){
    int cnt = 0;
    while(state){
        cnt += (state & 1);
        state >>= 1;
    }
    return cnt;
}
//                      前导0     上界 
ll dfs(int pos,int state,int lead,int limit,int k){
    if(pos == -1)
        return Getlen(state) == k;
    ll &dpnow = dp[pos][state][k];
    if(!limit && dpnow != -1)
        return dpnow;
    int max_digit = limit ? digit[pos] : 9;
    ll ans = 0;
    for(int i = 0; i <= max_digit; i++){
        ans += dfs((pos - 1), (lead && i == 0 ? 0 : Update(state,i)), (lead && i == 0), (limit && i == max_digit), k);
    }
    if(!limit)
        dpnow = ans;
    return ans;
}
 
ll solve(ll n,int k){
    int pos = 0;
    while(n){
        digit[pos++] = n % 10;
        n /= 10;
    }
    return dfs(pos-1,0,1,1,k);
}
int main(){
    int T,cas = 0;
    cin >> T;
    memset(dp,-1,sizeof(dp));
    while(T--){
        ll l,r;
        int k;
        cin >> l >> r >> k;
        cout << "Case #" << ++cas << ": ";
        cout << solve(r,k) - solve(l-1,k) << endl;
    }
    return 0;
}
上一篇:css样式积累


下一篇:luogu P3478 [POI2008]STA-Station 换根dp