题解 | #mixup2混乱的奶牛#
mixup2混乱的奶牛
https://ac.nowcoder.com/acm/problem/210981
本题算是状压dp的一个变形用法，在这里面将二进制位上的数从0变到1其实做得将牛放到末尾的操作，那么可以看到对于某一头牛他只关心前面一头牛是什么，前面牛到底有几种摆放方式和当前的牛无关。这符合动态规划的特性。
那么很容易得到状态转移方程为：dp[state|(1<<(i-1))][i] = dp[state|(1<<(i-1))][i]+dp[state][j]
值为方式数，放置的时候判断牛牛是否符合混乱即可。
//dp[state|(1<<(i-1))][i] = dp[state|(1<<(i-1))][i]+dp[state][j]
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 17;
int dp[1<<16][maxn];
int num[maxn];
int n, k;
signed main()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
{
cin>>num[i];
}
for (int i=0;i<n;i++)
{
dp[1<<i][i+1] = 1;
}
int len = (1<<n)-1;
for (int state=1;state<len;state++)
{
//遍历起点，一定是已经排过的牛
for (int i=1;i<=n;i++)
{
if (((state>>(i-1))&1)==0) continue;
for (int j=1;j<=n;j++)
{
if ((state>>(j-1))&1) continue;
if (abs(num[i]-num[j])<=k) continue;
dp[state|(1<<(j-1))][j] = dp[state|(1<<(j-1))][j]+dp[state][i];
}
}
}
int ans = 0;
for (int j=1;j<=n;j++)
{
ans += dp[len][j];
}
cout<<ans;
return 0;
}
查看29道真题和解析
