首页 > 其他 > 详细

BZOJ3591 最长上升子序列(状压dp)

时间:2018-09-26 13:27:30      阅读:204      评论:0      收藏:0      [点我收藏+]

  之前听说过一种dp套dp的trick,大致是用另一个dp过程中用到的一些东西作为该dp的状态。这个题有异曲同工之妙。

  考虑求LIS时用到的单调队列。设f[S]为所选取集合为S的方案数,其中在单调队列内的标2不在的标1。转移时考虑选择一个数是否合法,这只需要保证LIS长度不超过k且所给数的相对顺序不变。

  注意dp顺序,从小到大先枚举选了哪些数再枚举哪些在单调队列里。以及注意卡常。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<0||c>9) {if (c==-) f=-1;c=getchar();}
    while (c>=0&&c<=9) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define N 15
int n,m,id[N],p[N+1],f[15000000];
bool flag[1<<N][N];
int v[1<<N][N],c[1<<N],mx[1<<N],s[1<<N],ans=0;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj3591.in","r",stdin);
    freopen("bzoj3591.out","w",stdout);
    const char LL[]="%I64d\n";
#else
    const char LL[]="%lld\n";
#endif
    n=read(),m=read();
    for (int i=1;i<=m;i++) id[read()-1]=i;
    p[0]=1;for (int i=1;i<=n;i++) p[i]=p[i-1]*3;
    for (int i=0;i<(1<<n);i++)
        for (int j=0;j<n;j++)
        if (!(i&(1<<j)))
        {
            if (!id[j]) flag[i][j]=1;
            else
            {
                int tot=0;
                for (int k=0;k<n;k++)
                if ((i&(1<<k))) tot+=(id[k]>0);
                if (tot+1==id[j]) flag[i][j]=1;
            }
            int t=-1,x=0;
            for (int k=0;k<n;k++)
            if (i&(1<<k)) x+=p[k];
            for (int k=n-1;k>j;k--)
            if (i&(1<<k)) t=k;
            if (~t) v[i][j]=x-p[t]+p[j];
            else v[i][j]=x+p[j];
        }
        else c[i]+=p[j],mx[i]=max(mx[i],j),s[i]++;
    f[0]=1;
    for (int x=0;x<(1<<n);x++)
        for (int y=x;y>0||y==0&&x==0;x==0?y--:y=y-1&x)
        if (f[c[x]+c[y]])
        {
            int i=c[x]+c[y],z=c[x];
            for (int j=0;s[y]==m?j<mx[y]:j<n;j++)
            if (flag[x][j]) f[z+p[j]+v[y][j]]+=f[i];
            if (x==(1<<n)-1) ans+=f[i];
        }
    cout<<ans;
    return 0;
}

 

BZOJ3591 最长上升子序列(状压dp)

原文:https://www.cnblogs.com/Gloid/p/9703407.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!