P1896 [SCOI2005]互不侵犯 状压dp

时间：2023-01-19 00:33:33

正解：状压dp

解题报告：

看到是四川省选的时候我心里慌得一批TT然后看到难度之后放下心来觉得大概没有那么难

事实证明我还是too young too simple了QAQ难到爆炸TT我本来还想刚一道紫题搞完这个之后就佛了不做了TT

不扯淡了太太太浪费时间辣

好那直接港

首先我想到的就觉得大概是和那个奶牛玉米田的没有太大区别改一改就能ac！

然后我就先照着玉米田做完，发现过不了样例

于是改，改了半小时，好像差不多了，因为要存储放了几个国王巴拉巴拉的

还是没过样例，输出下过程，发现是上一种状态有很多种放国王的数量，又改改改改改

然后改到下课也没改完，心态爆炸，决定不做了第二天做

然后今天我又改了差不多半小时，总算ac了……开了两个三维数组三四个二维数组……太麻烦了TT

好的抱怨完了直接放程序吧quq

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(ll i=x;i<=y;i++)
ll zt[<<],cnt,num[<<],f[][<<][],cc[][<<][<<],ans=;][][<<];
//我jio得解释下这里其他就没有太多要港的辣？
//zt：合法状态
//cnt：有几个合法状态
//num：这个状态下放了几个国王
//f[i][j][k]:到第k行本层状态为j共计放了i个国王了的 合法方案数
//cc[i][j][k]:第i行状态为j时第k种可能的放了国王的数量 0存的是有几种可能的数量
//t[i][j][k]:就是个桶，是为了避免cc中存入重复的数量 意为：在第j行状态为k时数量为i是否存储过，若存储过自然不用处理，没有的话是要cc[0]++的嘛
//ans：就是最后的统计，明白吧？
//好的解释完了！那我觉得后面就没有那——么难理解辣！
ll read()
{
    ;;
    '))ch=getchar();
    ,ch=getchar();
    )+(x<<)+(ch^'),ch=getchar();
    return y?x:-x;
}
int cl(ll x)
{
    ;
    )
    {
        )t++;
        x>>=;
    }
    return t;
}
int main()
{
    ll n=read(),m=read();
    rp(i,,(<<n)-)
        ))==) && ((i&(i>>))==))zt[++cnt]=i,num[cnt]=cl(i),cc[][i][]=,cc[][i][]=num[cnt];//预处理 自己看不难理解
    rp(i,,cnt)f[num[i]][zt[i]][]=;//第一行要特殊处理
    rp(i,,n)
        rp(j,,cnt)
            rp(k,,cnt)
                ) && ((zt[j]&(zt[k]<<))==) && ((zt[j]&(zt[k]>>))==))//j为本行k为上一行状态
                    rp(q,,cc[i-][zt[k]][])//cc[balabala][balabala][q]枚举上一行状态为ztk时能放到的国王状态
                        ][zt[k]][q]+num[j]<=m)
                        {
                            f[cc[i-][zt[k]][q]+num[j]][zt[j]][i]+=f[cc[i-][zt[k]][q]][zt[k]][i-];//转移
                            ][zt[k]][q]+num[j]][i][zt[j]]==)//判断是否要加入cc0里面
                            {
                                cc[i][zt[j]][]++;
                                t[cc[i-][zt[k]][q]+num[j]][i][zt[j]]=;
                                cc[i][zt[j]][cc[i][zt[j]][]]=cc[i-][zt[k]][q]+num[j];
                            }
                        }
    rp(i,,cnt)ans+=f[m][zt[i]][n];
    printf("%lld",ans);
    ;
}
//完美结束yeah！

点我♂看♂灵巧在线wa题QAQ

哇我难得写这么多注释！不容易！好的那搞完了就去刚今天考试题目了TT

哎我太苦了好不容易逃脱状压dp又要进入考试题的深渊QAQ

相关文章