洛谷2915 奶牛混合起来Mixed Up Cows

Luogu

算法

首先发现奶牛的头数很少,仅有16头。

考虑状压DP。

设$f[i] [j]$表示j状态下i为最后一头牛的方案数,这样便可枚举下一头奶牛然后再DP。
那么:

$f[i][j]=\sum\{f[lastcow][j-(1<<i)]\}$

其中$lastcow$为倒数第二头奶牛的编号,$j-(1<<i)$即为没有$i$的状态。

答案为$\sum\{f[i] [(1<<n)-1]\}$,边界为$f[i] [1<<i]=1$(不难理解)。

还有,因为$2^0=1$,所以数组最好从$0$开始存。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
typedef long long LL;
const int MAXN=(1<<16)+10; 
int s[20],p,n;
LL f[20][MAXN];
int main()
{
    scanf("%d%d",&n,&p);
    for (re int i=0;i<n;i++) scanf("%d",&s[i]); //输入
    for (re int i=0;i<n;i++) f[i][1<<i]=1; //边界
    for (re int i=0;i<(1<<n);i++) //DP,枚举状态
        for (re int j=0;j<n;j++) //DP,枚举每头牛
        {
            if ((1<<j)&i) //如果在队中
            {
                for (re int k=0;k<n;k++) //DP,枚举每头牛
                    if (!(i&(1<<k))&&abs(s[k]-s[j])>p) //如果未出现且与最后一头牛的差>p
                        f[k][i|(1<<k)]+=f[j][i]; //累加方案数
            }
        }
    LL ans=0;
    for (re int i=0;i<n;i++) ans+=f[i][(1<<n)-1]; //统计答案
    cout<<ans<<endl; //输出
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 26 PM

发表评论