[數(shù)位dp+狀態(tài)壓縮] hdu 4352 XHXJ's LIS
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-10-13 00:13:40 閱讀次數(shù)：3477次
題意：
給x、y、k，在[x,y] 范圍內(nèi)最長(zhǎng)上升子序列長(zhǎng)度是k的數(shù)有幾個(gè)
思路：
模仿 LIS nlogn的想法，這里就只有10個(gè)數(shù)，進(jìn)行狀壓
然后直接搜就好了不用二分
然后按位dp下去就ok了！
代碼：
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
using namespace std;
//2014年9月26日09:46:04
__int64 dp[22][1024][11];
int num[22];
struct node
{
int n,l;
};
node js(int n,int x,int tep)
{
node ans;
ans.l=tep;
int i;
for(i=x; i<10; i++) if(n&(1<<i)) break;
if(i==10) //沒(méi)找到 長(zhǎng)度加一 填上那個(gè)數(shù)
{
ans.l=tep+1;
n|=(1<<x);
}
else //找到 更新那個(gè)數(shù)
{
n^=(1<<i);
n|=(1<<x);
}
ans.n=n;
return ans;
}
__int64 dfs(int site,int n,int l,int k,int zero,int f)
{
if(site==0)
{
if(zero) return 0;
return l==k;
}
if(!f&&!zero&&~dp[site][n][k]) return dp[site][n][k];
int len=f?num[site]:9;
__int64 ans=0;
for(int i=0; i<=len; i++)
{
node tep;
if(zero)
{
if(i==0) ans+=dfs(site-1,n,l,k,zero&&i==0,f&&i==len);
else
{
tep=js(n,i,l);
ans+=dfs(site-1,tep.n,tep.l,k,zero&&i==0,f&&i==len);
}
}
else
{
tep=js(n,i,l);
ans+=dfs(site-1,tep.n,tep.l,k,zero&&i==0,f&&i==len);
}
}
if(!f&&!zero) dp[site][n][k]=ans;
return ans;
}
__int64 solve(__int64 x,int k)
{
int cnt=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,0,k,1,1);
}
int main()
{
int t,cas=1;
cin>>t;
memset(dp,-1,sizeof(dp));
while(t--)
{
__int64 x,y;
int k;
scanf("%I64d%I64d%d",&x,&y,&k);
printf("Case #%d: %I64d
",cas++,solve(y,k)-solve(x-1,k));
}
return 0;
}
//2014年9月26日10:24:07
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
