BZOJ 4420二重镇题解

思路借鉴了这个博客：

我们可以想到状压dp

用一个十进制数来表示状态，即第i位表示位置i处的物品等级

用f[i][j][k]表示第i天，仓库的物品等级为j，状态为k时的最大收益

但是状态数貌似很多，开不下，同时上面的式子好像不太好转移

我们可以预处理出所有的合法状态，即无法消除的状态，然后在预处理出所有状态可能的转移，即枚举空位放那些等级的物品，用e[i][j][k]表示状态i，在第k个空位填等级为j的物品会转移到的状态编号，dis[i][j][k]表示这种转移所得到的收益，这样就方便转移了

注意到我们还要考虑到仓库中的物品，即会有f[i][j][k]转移到f[i][0][s]的情况，所以我们枚举第二维的顺序应该是倒序枚举(即最后考虑f[i][0]的状态）

细节有点多，注意不要写挂

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

const int mn = ;

const int maxn = ;

const int mx = ;//状态总数

char s[maxn];

int n,m,a[mn],b[mn],cnt,g[maxn];

int sit[mn],id[];

int e[mx][mn][mn],dis[mx][mn][mn],head[mx];

int xiao(int *a,int pos,int &val)

{

    val=;

    while(a[pos])

    {

        int tmp=a[pos],l=pos,r=pos;

        while(a[l]==a[l-] && l>) l--;

        while(a[r]==a[r+] && r<n) r++;

        if(l==r) break;

        val+=(r-l+)*(<<tmp);

        for(int i=l;i<=r;i++)

            a[i]=;

        a[pos]=(tmp+)%;

    }

    int tmp=;

    for(int i=;i<=n;i++)

        tmp=tmp*+a[i];

    if(!id[tmp]) id[tmp]=++cnt;

    return id[tmp];

}

void dfs(int x)

{

    //printf("%d\n",x);

    if(x>n)

    {

        int now = xiao(a,,b[]);

        for(int i=;i<=n;i++)

        {

            if(!a[i])

            {

                ++head[now];

                for(int j=;j<=;j++)

                {

                    for(int k=;k<=n;k++)

                        b[k]=a[k];

                    b[i]=j;

                    e[now][j][head[now]] = xiao(b,i,dis[now][j][head[now]]);

                }

            }

        }

        return ;

    }

    for(int i=;i<=;i++)

    {

        if(x== || !a[x-] || !i || a[x-]!=i)

        {

            a[x]=i;

            dfs(x+);

        }

    }

}

int f[maxn][mn][mx];

int dp()

{

    memset(f,-,sizeof(f));

    int ans=;

    f[][][]=;

    for(int i=;i<=m;i++)

        for(int k=;k>=;k--)

            for(int j=;j<=cnt;j++)

            {

                if(f[i][k][j]>=)

                {

                    if(i<m)

                    {

                        for(int s=;s<=head[j];s++)

                            f[i+][k][e[j][g[i+]][s]]=max(f[i+][k][e[j][g[i+]][s]],f[i][k][j]+dis[j][g[i+]][s]);

                    }

                    if(k)

                    {

                        for(int s=;s<=head[j];s++)

                            f[i][][e[j][k][s]]=max(f[i][][e[j][k][s]],f[i][k][j]+dis[j][k][s]);

                    }

                    else  f[i+][g[i+]][j]=max(f[i+][g[i+]][j],f[i][k][j]);

                    ans=max(ans,f[i][k][j]);

                }

            }

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    scanf("%s",s+);

    for(int i=;i<=m;i++)

        g[i]=s[i]-'';

    dfs();

    printf("%d\n",dp());

    return ;

}

巴特西

BZOJ 4420二重镇题解

最新文章

热门文章