卧薪尝胆,厚积薄发。
USACO2008 NOV mixup2 混乱的奶牛
Date: Tue Jul 17 10:18:43 CST 2018 In Category: NoCategory

Description:

求相邻两个数之差大于 $k$ 的数列个数。
$1\le n \le 16$

Solution:

状压一下就行了。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,k;
#define MAXN 17
int s[MAXN];
unsigned long long f[MAXN][1 << MAXN];
int main()
{
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;++i)scanf("%d",&s[i]);
int tot = (1 << n) - 1;
for(int i = 1;i <= n;++i)f[i][1 << (i - 1)] = 1ll;
for(int b = 1;b <= tot;++b)
{
for(int i = 1;i <= n;++i)
{
if(b & (1 << (i - 1)))
{
for(int j = 1;j <= n;++j)
{
if(!(b & (1 << (j - 1))))
{
if(abs(s[j] - s[i]) > k)
{
f[j][b | (1 << (j - 1))] += f[i][b];
}
}
}
}
}
}
unsigned long long ans = 0;
for(int i = 1;i <= n;++i)
{
ans += f[i][tot];
}
cout << ans << endl;
return 0;
}
In tag: DP-状压DP
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡