2021冲B层暑假集训Day5 DP专题

文章目录

展开

Day5 动态规划

零、什么是动态规划

简单来说，DP是一种决策方式。

这种决策方式需要每次决策依赖于当前状态，随机有引起状态的转移，从而获得一个决策序列。

基本思想就是，待解决的问题分成若干个子问题，依次求子问题的解，前一子问题的解为后一子问题提供有效的信息。在求解子问题时，列出所有可能的局部解，通过决策保留有可能达到最优的局部解。最后一个子问题就是初始子问题的解。

比如我们熟知的斐波那契数列 $f[n]$ ，我们都知道 $f[i]=f[i-1]+f[i-2]$ 。

那么假设我们的问题是求 $f[10]$ ，那么我们就可以分成求 $f[10],f[9],f[8]\dots$ 的子问题，而先求的子问题为后求的子问题提供了有效信息（即可以代入递推式子求解）。

当然这只是个例子，一个递推式子还谈不上用了动态规划。

动态规划三要素：

1.问题的阶段，比如上面的 $，，i，i-1，i-2\dots$

2.每个阶段的状态，也就是这个f数组所表示的状态

3.相邻阶段的递推关系，比如上面的 $f[i]=f[i-1]+f[i-2]$

当然我们也可以用二维的数组去表示一个状态，如

$f[i][j]$ 可以表示一个东西的状态在第i行第j列时，或一个东西的状态在取了i个点j条边。

动态规划的过程是：初始状态→决策1→决策2→…→决策n→终止状态

初始状态就是要知道某一位置的状态是已知的，比如上面例子中的 $f[0]=1,f[1]=1$ ；

终止状态就是要求答案的状态，比如上面例子中的 $f[10]$ 。

一、背包DP

（一）01背包

1.问题描述

有n个物品，容量为m的背包。第i个物品有价值vi和体积wi，想从n个物品中选出若干个装到背包里，体积和不能大于m，求价值和的最大值。

2.解决方法

我们用状态 $f[i][j]$ 表示我们已经考虑了前i个物品，选取的物品占了j的容量时，所能取到的最大价值。

对于第i个物品，我们可以考虑选它或者不选它来进行转移，如果选了的话，那么这个状态就是从 $f[i-1][j-w[i]]$ 来的；如果不选的话，这个状态就是从 $f[i-1][j]$ 来的。

即 $f[i][j]=max{f[i-1][j],(f[i-1][j-w[i]]+c[i])}$ 。

最后的答案就是 $max{f[n][0],f[n][1],\dots,f[n][m]}$ 。

#include<iostream>
using namespace std;
int n,m,w[1010],v[1010],f[1010][10010],ans;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        for(int j=w[i];j<=m;j++)//j从w[i]开始，防止数组越界
            f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
    }
    for(int i=0;i<=m;i++)
        ans=max(ans,f[n][i]);
    cout<<ans<<endl;
    return 0;
}

#include<iostream>

using namespace std;

int n,m,w[1010],v[1010],f[1010][10010],ans;

int main()

{

cin>>n>>m;

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

{

cin>>w[i]>>v[i];

for(int j=w[i];j<=m;j++)//j从w[i]开始，防止数组越界

f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);

}

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

ans=max(ans,f[n][i]);

cout<<ans<<endl;

return 0;

}

3.优化空间

（1）滚动数组

我们再来考虑斐波那契数列，我们要求 $f[i]$ 的话，只需要 $f[i-1]$ 和 $f[i-2]$ ，因此我们没有必要开 $f[n]$ 的数组，只需要开 $f[3]$ ： $f[0]=f[1],f[1]=f[2],f[2]=f[0]+f[1]$ ，循环下去即可。

（2）滚动数组优化01背包

我们来看 $f[i][j]$ ，如果将 $i$ 删掉的话：

f[j]=max(f[j],f[j-w[i]]+v[i]);

我们发现每层循环里的 $f[j]$ 依然是 $f[i][j]$ ，但是等号右边的 $f[j-w[i]]$ 却不一定是 $f[i-1][j-w[i]]$ ，因为正序枚举，在前面修改 $f[j1]$ 的值的时候可能恰巧修改到了 $f[j2-w[i]]$ ，即 $j1=j2-w[i]$ 。（此处j1<j2）

这样的话，我们就可能将一个物品选取多次。

那么修改方法就是：我们枚举j的时候倒序枚举。

我们知道，在上面的代码中倒序枚举和正序枚举没有叙别，但是在删掉 $f$ 后，倒序枚举让 $j1$ 不可能等于 $j2-w[i]$ 。（此处j1>j2），那么我们就可以使用一维的 $f[j]$ 进行背包了。

（3）例1：[NOIP2005普及组]采药：luoguP1048传送门

题目大意：一道裸的01背包。

实例代码：

#include<iostream>
using namespace std;
int n,m,w[1010],v[1010],f[10010],ans;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        for(int j=m;j>=w[i];j--)//j从w[i]开始，防止数组越界
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
    for(int i=0;i<=m;i++)
        ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}

#include<iostream>

using namespace std;

int n,m,w[1010],v[1010],f[10010],ans;

int main()

{

cin>>m>>n;

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

{

cin>>w[i]>>v[i];

for(int j=m;j>=w[i];j--)//j从w[i]开始，防止数组越界

f[j]=max(f[j],f[j-w[i]]+v[i]);

}

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

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

cout<<ans<<endl;

return 0;

}

（二）完全背包

1.问题描述

有n种物品，每种物品有无穷个，容量为m的背包。第i种物品有价值vi和体积wi，想从无穷个物品中选出若干个装到背包里，体积和不能大于m，求价值和的最大值。

2.解决方法

我们发现，完全背包和01背包的区别就是，01背包是有限个，而完全背包是有限种无限个。

我们刚刚在讨论优化空间时强调，顺序枚举 $j$ 的话可能将一个物品选取多次，而我们现在的目的就是将一个物品选取多次。

所以解决方法很简单，将01背包中逆序枚举 $j$ 改成正序枚举即可。

例2：疯狂的采药：luoguP1616传送门

题目大意：一道裸的完全背包，注意数据范围要开long long。

实例代码：

#include<iostream>
using namespace std;
int n,m,w[10010],v[10010];
long long f[10000010],ans;
long long max(int x,int y)
{
    return x>y?(long long)x:(long long)y;
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        for(int j=w[i];j<=m;j++)//j从w[i]开始，防止数组越界
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
    for(int i=0;i<=m;i++)
        ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}

#include<iostream>

using namespace std;

int n,m,w[10010],v[10010];

long long f[10000010],ans;

long long max(int x,int y)

{

return x>y?(long long)x:(long long)y;

}

int main()

{

cin>>m>>n;

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

{

cin>>w[i]>>v[i];

for(int j=w[i];j<=m;j++)//j从w[i]开始，防止数组越界

f[j]=max(f[j],f[j-w[i]]+v[i]);

}

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

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

cout<<ans<<endl;

return 0;

}

（三）多重背包

1.问题描述

有n种物品，容量为m的背包。第i种物品有价值vi和体积wi，第i种物品有ci个。想从sigma(ci)个物品中选出若干个装到背包里，体积和不能大于m，求价值和的最大值。

2.解决方法

我们发现这次的区别是每种物品的数目有限且不一定为1。

如果ci很小的话，我们可以把ci个物品拆成一个一个的物品进行01背包。

但如果ci很大呢，比如1000，那么就有1000000个物品。显然是不可行的。

这个问题有两种解法：

解法一：二进制拆分

我们考虑把k个物品利用二进制拆成logk个。

比如有某种物品有10个，那就可以拆成4个(1+2+4+3)，这样我们就可以组合出任意的物品数了。

如果我们想要8个物品，就可以取4个里的第一、三、四个。

这样我们就把ci拆成logci个了。这样就只有10000个物品。可能就可行了。

这种算法的复杂度是O(n·logci·m)的。

解法二：单调队列优化

我们考虑一个朴素的DP转移式：

$f[i][j]=max{f[i-1][j],(f[i-1][j-w[i]]+c[i]),(f[i-1][j-2\timesw[i]]+2\timesc[i]),\dots}$

我们考虑DP的 $j$ ，将%w[i]同余的 $j$ 单拎出来。

假设w[i]=4，c[i]=2。我们拎出%4=0的 $j$ 即 $f[i-1][0],f[i-1][4],f[i-1][8],f[i-1][12]\dots$

$f[i][0]$ 会从 $f[i-1][0]$ 转移过来；

$f[i][4]$ 可以从 $f[i-1][4]$ 转移过来，也可以从 $f[i-1][0]+c[i]$ 转移过来；

$f[i][8]$ 可以从 $f[i-1][8]$ 转移过来，也可以从 $f[i-1][4]+c[i]$ 转移过来，还可以从 $f[i-1][0]+2\timesc[i]$ 转移过来；

$f[i][12]$ 可以从 $f[i-1][12]$ 转移过来，也可以从 $f[i-1][8]+c[i]$ 转移过来，还可以从 $f[i-1][4]+2\timesc[i]$ 转移过来，但值得注意的是，此时是不可以由 $f[i-1][0]+3\timesc[i]$ 转移来的，因为c[i]=2，这个物品只有两个。

这样看下来，我们仿佛看到了一个长度为2的窗口在滑，且每次需要的是窗口内最大的值来进行转移，所以我们可以考虑单调队列。

大家可以手动模拟一下单调队列的过程，加c[i]的系数可以通过j的值来计算。

然后对于%4=1,%4=2,%4=3的情况也一样，我们发现都跑完之后恰好把所有的情况都跑了一遍。

因此这个算法的复杂度是O(n·m)的。

例3：宝物筛选：luoguP1776传送门

单调队列优化代码：

#include <iostream>
using namespace std;
int n,W;
int ans=0,temp=0;
int dp[40010],q[40010],q2[40010];
int main()
{
    cin>>n>>W;
    for(int i=1;i<=n;i++)//每组
    {
        int v,w,m;
        cin>>v>>w>>m;
        if(w==0)
        {
            ans+=m*v;
            continue;
        }
        int k,head,rear;
        m=min(W/w,m);//最大可用数量
        for(int j=0;j<w;j++)//枚举余数
        {
            head=1,rear=0;
            k=(W-j)/w;
            for(int o=0;o<=k;o++)//枚举同余个数
            {
                while(head<=rear&&dp[j+o*w]-o*v>=q2[rear])rear--;
                q[++rear]=o;
                q2[rear]=dp[j+o*w]-o*v;
                while(head<=rear&&q[head]+m<o)head++;
                dp[j+o*w]=max(dp[j+o*w],q2[head]+o*v);
                temp=max(temp,dp[j+o*w]);
                //cout<<j<<" "<<o<<" "<<q[head]<<" "<<q[rear]<<" "<<dp[j+q[head]*w]+v*(o-q[head])<<" "<<dp[j+q[rear]*w]+v*(o-q[rear])<<endl;
            }
        }
    }
    cout<<ans+temp<<endl;
    return 0;
}

#include <iostream>

using namespace std;

int n,W;

int ans=0,temp=0;

int dp[40010],q[40010],q2[40010];

int main()

{

cin>>n>>W;

for(int i=1;i<=n;i++)//每组

{

int v,w,m;

cin>>v>>w>>m;

if(w==0)

{

ans+=m*v;

continue;

}

int k,head,rear;

m=min(W/w,m);//最大可用数量

for(int j=0;j<w;j++)//枚举余数

{

head=1,rear=0;

k=(W-j)/w;

for(int o=0;o<=k;o++)//枚举同余个数

{

while(head<=rear&&dp[j+o*w]-o*v>=q2[rear])rear--;

q[++rear]=o;

q2[rear]=dp[j+o*w]-o*v;

while(head<=rear&&q[head]+m<o)head++;

dp[j+o*w]=max(dp[j+o*w],q2[head]+o*v);

temp=max(temp,dp[j+o*w]);

//cout<<j<<" "<<o<<" "<<q[head]<<" "<<q[rear]<<" "<<dp[j+q[head]*w]+v*(o-q[head])<<" "<<dp[j+q[rear]*w]+v*(o-q[rear])<<endl;

}

cout<<ans+temp<<endl;

return 0;

}

二进制拆分代码：

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,ans,cnt=1;
int f[1000005];
int w[1000005],v[1000005];
int main()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        for(int j=1;j<=c;j*=2)
        {
            v[++cnt]=j*a;
            w[cnt]=j*b;
            c-=j;
        }
        if(c) 
        {
            v[++cnt]=a*c;
            w[cnt]=b*c;
        }
    }

    for(int i=1;i<=cnt;++i)
     for(int j=m;j>=w[i];--j)
      f[j]=max(f[j],f[j-w[i]]+v[i]);
    printf("%dn",f[m]);
    return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int n,m,ans,cnt=1;

int f[1000005];

int w[1000005],v[1000005];

int main()

{

int a,b,c;

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

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

{

scanf("%d%d%d",&a,&b,&c);

for(int j=1;j<=c;j*=2)

{

v[++cnt]=j*a;

w[cnt]=j*b;

c-=j;

}

if(c)

{

v[++cnt]=a*c;

w[cnt]=b*c;

}

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

for(int j=m;j>=w[i];--j)

f[j]=max(f[j],f[j-w[i]]+v[i]);

printf("%dn",f[m]);

return 0;

}

（四）分组背包

1.题目描述

现在有n组物品，每组物品有ci件，第i组的第j件的体积是wij，价值是vij，背包容量m。现在要求取若干个物品，要求总体积不能大于背包容量，且每组物品里最多只能取一个，求最大价值。

2.解决方法

这种题的不同在于，物品和物品之间是有限制的。

我们考虑一种暴力的做法就是，我们枚举每一组，对于第一个分组的物品，如果取了的话，就直接判断下一组的物品，否则判断该组的下一种物品。

也就是说，这里的 $f[i][j]$ 表示的是前i组物品花费v时的最大价值。

则 $f[i][j]=max{f[i-1][j],f[i-1][j-c[k]]+w[i]}$ ，其中物品k是属于第i组的。也就是说，我们取 $f[i][j]$ 时，取出的是第i组里最优的那一个物品。

例4：通天之分组背包：luoguP1757传送门

题目大意：分组背包裸题

实例代码：

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>m>>n;
    int a[1010]={0},b[1010]={0},f[1010]={0},c[110][20]={0},cnt[110]={0},cmax=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>a[i]>>b[i]>>x;
        cmax=max(cmax,x);
        cnt[x]++;
        c[x][cnt[x]]=i;
    }
    for(int i=1;i<=cmax;i++)
    {
        for(int j=m;j>=0;j--)
        {
            for(int k=1;k<=cnt[i];k++)
            {
                if(j>=a[c[i][k]])
                    f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n,m;

cin>>m>>n;

int a[1010]={0},b[1010]={0},f[1010]={0},c[110][20]={0},cnt[110]={0},cmax=0;

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

{

int x;

cin>>a[i]>>b[i]>>x;

cmax=max(cmax,x);

cnt[x]++;

c[x][cnt[x]]=i;

}

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

{

for(int j=m;j>=0;j--)

{

for(int k=1;k<=cnt[i];k++)

{

if(j>=a[c[i][k]])

f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);

}

cout<<f[m]<<endl;

return 0;

}

当然背包里还有一些附件问题的题，大家需要具体问题具体分析。

二、树形DP

（一）树形DP的实现

树形DP的状态是，对于第i个结点，有 $f[i][j]$ 的状态，表示以i为根的子树上满足j条件时的最优解，j可以是选择j个结点，或者是删除j条边等等。

（二）为什么要用树形DP

树这种结构可以很好的判断某点与其附属结点的关系，而且可以递归的用儿子修改父亲的值。

前者可以对应解题，后者正是DP的精髓。

（三）例题时间

1.没有上司的舞会

我们先来看一道经典的例题：没有上司的舞会：luoguP1352传送门

题目大意：有n个职员要参加舞会。n个职员有像树一样的从属关系，这导致除老板（根节点）他们都有一个直接上司。我们知道每个员工都有欢乐值，但是如果某个员工的直接上司来参加了，他就一定不会来。现在让我们求满足要求的欢乐值最大值。

解题思路：我们设 $f[i][0]$ 表示以i为根的子树上如果 $i$ 不参加舞会的最大值，设 $f[i][1]$ 表示以i为根的子树上如果 $i$ 参加舞会的最大值。那么我们可以显然知道：（j表示i的直接下属）

$f[i][0]=sigma{max{f[j][0],f[j][1]}}$ ，即如果第i个人不来，那就可以考虑他的直接下属来还是不来。

$f[i][1]=sigma{f[j][0]}$ ，即如果第i个人来了，那么就让他的直接下属都不来了。

最后答案就是 $max{f[root][0],f[root][1]}$ 。

实例代码：

#include <iostream>
using namespace std;
int n;
int f[6010][5];
int head[6010],nxxt[6010],ru[6010],root;
void dp(int x)
{
    for(int i=head[x];i;i=nxxt[i])
    {
        dp(i);
        f[x][1]+=f[i][0];
        f[x][0]+=max(f[i][0],f[i][1]);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>f[i][1];
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>b>>a;
        ru[b]++;
        nxxt[b]=head[a];
        head[a]=b;
    }
    for(int i=1;i<=n;i++)
    {
        if(ru[i]==0)
        {
            root=i;
            break;
        }
    }
    dp(root);
    cout<<max(f[root][1],f[root][0])<<endl;
    return 0;
}

#include <iostream>

using namespace std;

int n;

int f[6010][5];

int head[6010],nxxt[6010],ru[6010],root;

void dp(int x)

{

for(int i=head[x];i;i=nxxt[i])

{

dp(i);

f[x][1]+=f[i][0];

f[x][0]+=max(f[i][0],f[i][1]);

}

int main()

{

cin>>n;

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

cin>>f[i][1];

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

{

int a,b;

cin>>b>>a;

ru[b]++;

nxxt[b]=head[a];

head[a]=b;

}

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

{

if(ru[i]==0)

{

root=i;

break;

}

dp(root);

cout<<max(f[root][1],f[root][0])<<endl;

return 0;

}

2.时态同步

我们再来看一道稍微进阶一点的例题：时态同步：luoguP1131传送门

题目大意：有一棵树，树上的边有边权。所有根到所有叶子结点的距离都可求。现在有一个操作Q可以使某一条边的边权加一，问最少经过多少次操作Q使得根到所有叶子结点的距离都相同。

解题思路：我们考虑状态f[i]表示以i为根的子树最多需要多少次操作，并维护一个数组maxn[i]表示以i为根的子树到叶子结点距离的最大值。那么我们就有状态转移方程：

$f[u]=sigma{f[v]+maxn[u]-w[u,v]-maxn[v]}$ ，其中u，v分别是一条边的起点和终点，w[u,v]表示这条边的长度。然后我们进行树上DP就可以了。

实例代码：

#include <iostream>
using namespace std;
int n,s;
int head[500010],nxxt[1000010],to[1000010],val[1000010];
long long f[500010],maxn[500010];
int cnt;
void add(int u,int v,int w)
{
    nxxt[++cnt]=head[u];
    to[cnt]=v;
    val[cnt]=w;
    head[u]=cnt;
}
//f[u]=f[v]+maxn[u]-w[u,v]-maxn[v]
void dp(int x,int fa)
{
    f[x]=0;
    maxn[x]=0;
    for(int i=head[x];i;i=nxxt[i])
    {
        if(to[i]==fa)continue;
        dp(to[i],x);
        maxn[x]=max(maxn[to[i]]+val[i],maxn[x]);
    }
    for(int i=head[x];i;i=nxxt[i])
    {
        if(to[i]==fa)continue;
        f[x]+=(f[to[i]]+maxn[x]-val[i]-maxn[to[i]]);
    }
}
int main()
{
    cin>>n>>s;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dp(s,0);
    cout<<f[s]<<endl;
    return 0;
}

#include <iostream>

using namespace std;

int n,s;

int head[500010],nxxt[1000010],to[1000010],val[1000010];

long long f[500010],maxn[500010];

int cnt;

void add(int u,int v,int w)

{

nxxt[++cnt]=head[u];

to[cnt]=v;

val[cnt]=w;

head[u]=cnt;

}

//f[u]=f[v]+maxn[u]-w[u,v]-maxn[v]

void dp(int x,int fa)

{

f[x]=0;

maxn[x]=0;

for(int i=head[x];i;i=nxxt[i])

{

if(to[i]==fa)continue;

dp(to[i],x);

maxn[x]=max(maxn[to[i]]+val[i],maxn[x]);

}

for(int i=head[x];i;i=nxxt[i])

{

if(to[i]==fa)continue;

f[x]+=(f[to[i]]+maxn[x]-val[i]-maxn[to[i]]);

}

int main()

{

cin>>n>>s;

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

{

int u,v,w;

cin>>u>>v>>w;

add(u,v,w);

add(v,u,w);

}

dp(s,0);

cout<<f[s]<<endl;

return 0;

}

三、状压DP

（一）什么是状态压缩动态规划

状压一般适用于在n×n的棋盘上进行操作。

状压DP是将状态用二进制的方法存起来。

比如我们有一个9×9的棋盘，那么某一行的棋子方法就可以用一个数字去表示：比如 $(283)_{10}$ 就可以表示成：

列数	1	2	3	4	5	6	7	8	9
二进制	1	0	0	0	1	1	0	1	1
是否放	是	否	否	否	是	是	否	是	是

由此我们可见，一个状态只需要 $2^{n+1}-1$ 的十进制数就可以表示。

我们还发现这样的话会遍历每种状态，而一行最多有 $2^n$ 种状态，所以我们会发现一般这种题的n值都很小。（如果太大的话也不好用十进制数表示）

（二）一些二进制小技巧

与或非，异或，位运算就不再多说了。

1.判断一个数字x二进制下第i位是不是1

if(((1<<(i-1))&x)>0)：将1左移i-1位，相当于制造了一个只有第i位是1，其他位都是0的数。再与x做与运算，如果结果大于0，则说明x二进制下第i位是1.

2.将一个数字x二进制第i位变成1

x=x|(1<<(i-1))：证法类似1.

3.将一个数字x二进制第i为变成0

x=x&~(1<<(i-1))：证法类似1.

4.把一个数字二进制下最靠右的第一个1去掉

x=x&(x-1)：手推一下很好找规律。

（三）例题时间

1.互不侵犯

经典的状压DP题：互不侵犯：luoguP1896传送门

题目大意：N×N的棋盘放k个国王，国王能攻击到与自己相邻的八个格子。问有多少种摆放方案使他们互不攻击

解决思路：

实例代码：

#include <iostream>
using namespace std;
int n,kk;
int zt[1000],gs[1000],cnt=0;
long long f[10][1000][100];
void dfs(int x,int sum,int lie)
{
    if(lie>n)
    {
        zt[++cnt]=x;
        gs[cnt]=sum;
        //cout<<x<<" "<<sum<<endl;
        return ;
    }
    dfs(x,sum,lie+1);
    dfs(x|(1<<(n-lie)),sum+1,lie+2);
}
int main()
{
    cin>>n>>kk;
    dfs(0,0,1);
    for(int i=1;i<=cnt;i++)
        f[1][i][gs[i]]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            for(int k=1;k<=cnt;k++)
            {
                if((zt[j]&zt[k])||((zt[j]<<1)&zt[k])||((zt[j]>>1)&zt[k]))continue;
                for(int o=gs[j];o<=kk;o++)
                    f[i][j][o]+=f[i-1][k][o-gs[j]];
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=cnt;i++)ans+=f[n][i][kk];
    cout<<ans<<endl;
    return 0;
}

#include <iostream>

using namespace std;

int n,kk;

int zt[1000],gs[1000],cnt=0;

long long f[10][1000][100];

void dfs(int x,int sum,int lie)

{

if(lie>n)

{

zt[++cnt]=x;

gs[cnt]=sum;

//cout<<x<<" "<<sum<<endl;

return ;

}

dfs(x,sum,lie+1);

dfs(x|(1<<(n-lie)),sum+1,lie+2);

}

int main()

{

cin>>n>>kk;

dfs(0,0,1);

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

f[1][i][gs[i]]=1;

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

{

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

{

for(int k=1;k<=cnt;k++)

{

if((zt[j]&zt[k])||((zt[j]<<1)&zt[k])||((zt[j]>>1)&zt[k]))continue;

for(int o=gs[j];o<=kk;o++)

f[i][j][o]+=f[i-1][k][o-gs[j]];

}

long long ans=0;

for(int i=1;i<=cnt;i++)ans+=f[n][i][kk];

cout<<ans<<endl;

return 0;

}