程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4352 XHXJ's LIS 數位dp

HDU 4352 XHXJ's LIS 數位dp

編輯:關於C++

 

題意:

一個數自身的最長子序列=每一位都是一個數字然後求的LIS

問區間內有多少個數 自身的最長子序列==k

思路:

因為自身的最長子序列至多=10,且由0~9組成,所以狀壓10個二進制表示0~9中哪些數字已經用過

dp[i][j] 表示長度為i的數字,最長子序列中出現的數字狀態j的方法數。由於詢問數=K,也存下來避免重復計算。

 

 

 

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 66;
int siz[1 << 10], nex[1 << 10][10]; // nex[i][j]表示已經用了i狀態的序列,再加入數字j且使得序列狀態不變會變成的狀態
int bit[20], K;
//因為K只有10,所以構成這個序列的最長也就是0~9,所以用一個二進制表示0~9中哪些已經用過了
ll dp[N][1<<10][11];//dp[len][high][state][lis];長度為len,最高位為high,已使用過的有效子序列的狀態為state,最長上升子序列為lis
ll dfs(int len, int state, bool zero, bool flag){
	if (len == 0)return siz[state] == K;
	if (!flag && dp[len][state][K] != -1)return dp[len][state][K];

	ll ans = 0;
	int end = flag ? bit[len] : 9;
	for (int i = 0; i <= end; i++)
		ans += dfs(len - 1, (zero&&i == 0) ? 0 : nex[state][i], zero&&i == 0, flag&&i == end);

	if (!flag)dp[len][state][K] = ans;
	return ans;
}

ll solve(ll x){
	int len = 0;
	for (ll tmp = x; tmp; tmp /= 10)bit[++len] = tmp % 10;
	return dfs(len, 0, 1, 1);
}
int find_nex(int status, int num){
	for (int i = num; i < 10; i++)
	if (status&(1 << i))return(status ^ (1 << i)) | (1 << num);
	return status | (1 << num);
}

int main() {
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < 1 << 10; i++){
		siz[i] = 0;
		for (int j = 0; j < 10; j++)
		{
			if (i&(1 << j))siz[i]++;
			nex[i][j] = find_nex(i, j);
		}
	}
	int T, Cas = 1; scanf(%d, &T);
	while (T-- > 0){
		ll l, r;
		cin >> l >> r >> K;
		printf(Case #%d: %I64d
, Cas++, solve(r) - solve(l - 1));
	}
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved