NOIP 模拟 $24\; \rm matrix$

题解 $by\;zj\varphi$

发现 $\rm n,m$ 都很小，考虑分行状压。

但是上一行和下一行的按钮状态会对当前行造成影响，所以再枚举一个上一行的按钮状态。

因为对于两行，只有如下三种情况是合法的

\[0\;1\;1\\
1\;1\;0
\]

所以总复杂度为 $\mathcal O(n2^n3^n)$，最后统计答案时记得最后一行没有下一行来覆盖它，所以它自身的覆盖情况一定要覆盖全。

Code:

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++;

    template<typename T>inline void read(T &x) {

        ri f=1;x=0;register char ch=getchar();

        while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=getchar();};

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

        x=f?x:-x;

    }

}

using IO::read;

namespace nanfeng{

    #define FI FILE *IN

    #define FO FILE *OUT

    template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}

    template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}

    static const int N=11,INF=1061109567;

    int dp[N][1<<N][1<<N],g[N][1<<N],vis[N],mo[N],n,m,ans=INT_MAX;

    char s[N+2];

    inline int main() {

        //FI=freopen("nanfeng.in","r",stdin);

        //FO=freopen("nanfeng.out","w",stdout);

        read(n),read(m);

        for (ri i(1);i<=n;p(i)) {

            scanf("%s",s+1);

            for (ri j(1);j<=m;p(j)) vis[i]|=(s[j]=='1')<<j-1;

        }

        int bs=(1<<m)-1;

        for (ri i(1);i<=n;p(i)) {

            for (ri j(1);j<=m;p(j)) read(mo[j]);

            for (ri j(0);j<=bs;p(j)) {

                ri tmp=0;

                for (ri k(0);k<m;p(k)) if ((j>>k)&1) tmp+=mo[k+1];

                g[i][j]=tmp;

            }

        }

        memset(dp,0x3f,sizeof(dp));

        memset(dp[0],0,sizeof(dp[0]));

        for (ri i(0);i<=bs;p(i)) {

            int tmp=vis[1]|((i<<1|i>>1)&bs)|i;

            dp[1][tmp][i]=g[1][i];

        }

        for (ri i(1);i<n;p(i)) {

            for (ri j(0);j<=bs;p(j)) {

                for (ri l(0);l<=bs;p(l)) {

                    if ((l|j)!=bs) continue;

                    for (ri k(0);k<=bs;p(k)) {

                        if (dp[i][j][k]==INF) continue;

                        int tmp=vis[i+1]|k|((l<<1|l>>1)&bs)|l;

                        dp[i+1][tmp][l]=cmin(dp[i+1][tmp][l],dp[i][j][k]+g[i+1][l]);

                    }

                }

            }

        }

        for (ri i(0);i<=bs;p(i)) ans=cmin(ans,dp[n][bs][i]);

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

        return 0;

    }

}

int main() {return nanfeng::main();}

巴特西

NOIP 模拟 $24\; \rm matrix$

题解 \(by\;zj\varphi\)

最新文章

热门文章