[USACO] 奶牛混合起来 Mixed Up Cows

题目描述

Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 200

约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍， 而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？

题目解析

本来想打状压搜索的，结果分析了一下发现会T。

看到一个特别好的思路，记在这里

相比于考虑用几个奶牛，再枚举两重状态的三循环来说，我们可以考虑先枚举状态，再枚举状态里用过的牛哪个在队伍最后。这样只要两重循环就可以了，效率比原来高多了。

 dp[i][j]表示用了i个牛，状态是j（01串）

注意开longlong，这题很坑

Code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int n,m;
long long ans;
int s[20];
long long dp[20][(1<<16)];

void init() {
    for(int i = 1; i <= n; i++) {
        dp[i][1<<(n-i)] = 1;
    }
    return;
}

bool judge(int j,int k) {
    if(k == j) return false;
    if(abs(s[j] - s[k]) > m) return true;
    else return false;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&s[i]);
    }
    init();
    int tmp;
    for(int i = 1; i < (1 << n); i++) {
        for(int j = 1; j <= n; j++) {
            if(dp[j][i]) continue;
            if(i & (1 << (n - j))) {
                tmp = i ^ (1 << (n - j));
                for(int k = 1; k <= n; k++) {
                    if(judge(k,j)) dp[j][i] += dp[k][tmp];
                }
            }
        }
    }
    for(int i = 1;i <= n;i++) {
        ans += dp[i][(1<<n)-1];
    }
    printf("%lld",ans);
    return 0;
}