Luogu P2915 [USACO08NOV]奶牛混合起来

题外话：

是非常颓废的博主

写题解也不在于能不能通过啦，主要是缓解颓废

首先看到这个题，肯定是可以暴力搜索的：

不得不说这道题还是很善良的，一波大暴力dfs，居然有70pts：



#include<bits/stdc++.h>

using namespace std;

inline int read() {

    int ans=0;

    char last=' ',ch=getchar();

    while(ch>'9'||ch<'0') last=ch,ch=getchar();

    while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,k;

int s[20];

long long ans;

bool vis[20];

void dfs(int cnt,int nxt) {

    if(cnt==n) {

        ans++;

        return;

    }

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

        if(vis[i]) continue;

        if(abs(s[i]-nxt)>k) {

            vis[i]=1;

            dfs(cnt+1,s[i]);

            vis[i]=0;

        }

    }

}

int main() {

    n=read();

    k=read();

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

        s[i]=read();

    dfs(0,-k-1);

    printf("%lld",ans);

    return 0;

}

想改记忆化，然后我发现我不会

滚回来重新考虑dp：

将奶牛状压到一个二进制数中，第i位表示这头奶牛是否在队伍中；（突兀

我们设 \(dp[i][j]\) 表示当前状态为i，最后一个加入队伍的奶牛是j的方案数；

考虑如何转移：

设现在的状态为 \(dp[i][j]\)

考虑枚举下一个加入队伍的奶牛g是哪一只，那么首先肯定要满足的，就是这只奶牛不能已经加入队伍了（奶牛：我有分身术也就是i&(1<<(g-1))==0

1.如果已经在队伍里，显然要continue；（废话

2.如果不在队伍里，那么判断第g头奶牛和第j头奶牛之间的编号之差是否>k,同样的不是就continue掉（同样的废话

如果上面两个条件都满足，那么就可以将g加入队伍，对应的状态 \(dp[i|(1<<(g-1))][g]+=dp[i][j];\)

考虑初始化：

对于只有一头奶牛的情况，显然只有一种方案，因此 \(dp[1<<(i-1)][i]=1;\)

然后因为上面讲的非常非常之乱，咱们来理一理思路：

首先显然是初始化，将只有一头奶牛的方案的值初始化为1

接下来枚举每一种状态

第二维枚举当前状态下，最后一个加入队伍的奶牛j是哪一只（可以直接从1~n枚举，用i&(1<<(j-1))!=0来判断合法与否

然后枚举下一头加入队伍的奶牛是哪一头，判断是否符合上面的两个条件，相应的进行修改

最后显然是输出答案啦:显然最后的答案应该是所有奶牛都加入了队伍，每一头奶牛最后进入队伍的方案数相加，也就是 \(\sum\limits_{i=1}^n dp[(1<<n)-1][i]\)

然后，大概应该可能就可以愉快的AC了？（是码风清奇的奇女子，将就着看吧



#include<bits/stdc++.h>

using namespace std;

inline int read() {

    int ans=0;

    char last=' ',ch=getchar();

    while(ch>'9'||ch<'0') last=ch,ch=getchar();

    while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,k;

int s[20];

long long ans;

long long dp[70000][18];

int main() {

    n=read();

    k=read();

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

        s[i]=read();

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

        dp[1<<(i-1)][i]=1;

    for(int a=1;a<(1<<n);a++) {

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

            if(!(a&(1<<(j-1))))

                continue;

            for(int g=1;g<=n;g++) {

                if((a&(1<<(g-1))))

                    continue;

                if(abs(s[j]-s[g])<=k)

                    continue;

                dp[a|(1<<(g-1))][g]+=dp[a][j];

            }

        }

    }

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

        ans+=dp[(1<<n)-1][i];

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

    return 0;

}

//一堆括号看的我眼疼

巴特西

Luogu P2915 [USACO08NOV]奶牛混合起来

最新文章

热门文章