caioj1421&&hdu2167: [视频]【状态压缩】选数

%hz大佬。。这道题的状态压缩简直匪夷所思（其实是我孤陋寡闻，而且我以前的博客竟然写了这题。。水啊）

嗯这题可以发现，我们可以用一个二进制表示一行的状态，1表示选0反之，可以发现行与行之间可选的范围是确定的，比如说：
100
这样的状态适用于每一行，推广一下：
100
001
是适用于任何两行之间的。所以我们可以先将所有成立的状态求出来，要求就是左移一位和右移一位和原状态&运算为0，这样保证每个1左右都没有1。然后枚举行、状态，可以继承的状态，继承可以继承的状态的最大值，然后加上这一行的得到的值即可。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

int n,mp[][];

int ol,o[],f[][];

bool bj(int x,int y)

{

    return ((x&y)==)?true:false;

}

int hehe(int k,int x)

{

    int tp=,ans=;

    while(x!=)

    {

        tp++;

        if(x%==)ans+=mp[k][tp];

        x/=;if(tp==n)break;

    }

    return ans;

}

int main()

{

    scanf("%d",&n);

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

    {

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

            scanf("%d",&mp[i][j]);

        t=t*;

    }

    o[++ol]=;f[][]=;

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

        if(bj(i,i/)==true&&bj(i,i*)==true)

        {

            o[++ol]=i;

            f[][i]=hehe(,i);

        }

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

    {

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

        {

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

            {

                if(bj(o[i],o[j])==true&&bj(o[i],o[j]/)==true&&bj(o[i],o[j]*)==true)

                {

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

                }

            }

            f[k][o[i]]+=hehe(k,o[i]);

        }

    }

    int ans=;

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

        if(f[n][o[i]]>ans)ans=f[n][o[i]];

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

    return ;

}

巴特西

caioj1421&&hdu2167: [视频]【状态压缩】选数

最新文章

热门文章