首页 > 代码库 > HDU 4996 Revenge of LIS(DP)
HDU 4996 Revenge of LIS(DP)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4996
题意：求1到n的全排列中，有多少个排列的最长上升子列长度为K？
思路：对于当前的最长上升子列，我们记录最后一个值得最小值即可。因此我们用2^n的状态表示当前最长上升子列中使用了哪些数字，且字典序最小。前n-1个数字之后，我们枚举最后一个位置的数字为[1,n]中每个数字，设为k，那么我们只要将前面[1,n-1]组成的数列中所有大于等于k的数字加一即可。
int n,k;i64 f[22][22];i64 dp[1<<22],tmp[1<<22];int cal(int x){ int ans=0; int i; for(i=0;i<20;i++) if(x&(1<<i)) ans++; return ans;}void init(){ dp[1]=1; f[1][1]=1; int i,j; for(i=1;i<18;i++) { for(j=0;j<(1<<i);j++) tmp[j]=dp[j]; for(j=0;j<(1<<(i+1));j++) dp[j]=0; for(j=0;j<(1<<i);j++) if(tmp[j]) { int k; for(k=0;k<=i;k++) { int tot=0; int c[20]; int t; for(t=0;t<i;t++) if(j&(1<<t)) c[tot++]=t; for(t=0;t<tot;t++) if(c[t]>=k) c[t]++; c[tot++]=k; for(t=0;t<tot;t++) if(c[t]>k) { c[t]=k; break; } int st=0; for(t=0;t<tot;t++) st|=1<<c[t]; dp[st]+=tmp[j]; } } for(j=0;j<(1<<(i+1));j++) f[i+1][cal(j)]+=dp[j]; }}int main(){ init(); int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); printf("%I64d\n",f[n][k]); }}
HDU 4996 Revenge of LIS(DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。