技术教程 编程教程 bzoj1231 [Usaco2008 Nov]mixup2 混乱的奶牛——状压DP 正文

bzoj1231 [Usaco2008 Nov]mixup2 混乱的奶牛——状压DP

2023-06-25,,

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1231

小型状压DP；

f[i][j] 表示状态为 j ，最后一个奶牛是 i 的方案数；

所以下一个只能是和它相差大于 k 而且不在状态中的奶牛。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

int n,m,s[];

ll ans,f[][<<];

int abss(int x){return (x>)?x:-x;}

int main()

{

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

    int mx=(<<n);

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

    {

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

        f[i][<<(i-)]=;

    }

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

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

        {

            if(!((<<(j-))&i))continue;

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

            {

                if((<<(k-))&i)continue;

                if(abss(s[k]-s[j])>m)f[k][i|(<<(k-))]+=f[j][i];

            }

        }

    for(int i=;i<=n;i++)ans+=f[i][mx-];

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

    return ;

}

bzoj1231 [Usaco2008 Nov]mixup2 混乱的奶牛——状压DP的相关教程结束。

《bzoj1231 [Usaco2008 Nov]mixup2 混乱的奶牛——状压DP.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!