bzoj usaco 1231

最新推荐文章于 2024-11-29 22:14:32 发布

mars_ch

最新推荐文章于 2024-11-29 22:14:32 发布

阅读量260

点赞数

分类专栏： bzoj

本文链接：https://blog.csdn.net/mars_ch/article/details/52946184

版权

bzoj 专栏收录该内容

34 篇文章

订阅专栏

本文介绍了一种使用状态压缩动态规划（状压DP）解决特定类型问题的方法。通过一个具体的例子展示了如何定义状态，列出状态转移方程，并给出完整的C++代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

新的状压dp姿势get√

看到这题想到了dp但是发现不会列dp方程。

~~遂看了看题解~~

然后状压很棒。。

f[i][j]表示以i为结尾的状态为j的方案数。何为状态就是哪些牛选了哪些牛没有选。相当于我们有一个队列。每回有一个元素往里加。
所以
初始状态：f[i][1<<(i-1)]=1; //一开始就一头牛在队列里
转移：f[k][i|(1<<(k-1))]+=f[j][i] 当然j在状态i中，k不在并且k j编号符合要求
结果统计

\sum i = 1 n i = f [i] [t o t]

$\sum_{i=1}^n i = f[i][tot]$ tot即为总公式。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define int long long
using namespace std;
//by mars_ch
int f[20][1<<18];
int a[20];
int n,K;
signed main()
{
    scanf("%lld%lld",&n,&K);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        f[i][1<<(i-1)]=1;
    }
    int tot=(1<<n)-1;
    for(int i=0;i<=tot;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i&(1<<(j-1)))
            {
                for(int k=1;k<=n;k++)
                {
                    if((i|(1<<(k-1)))!=i && abs(a[j]-a[k])>K)
                    {
                        f[k][i|(1<<(k-1))]+=f[j][i];
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=f[i][tot];
    }
    printf("%lld\n",ans);
}