求助个题
  • 板块学术版
  • 楼主A_Đark_Horcrux
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/9/10 20:34
  • 上次更新2023/11/5 13:27:30
查看原帖
求助个题
54372
A_Đark_Horcrux楼主2020/9/10 20:34

输入n个数字和一个数字k 求任意两个相邻数字之差都大于k的排列数 n≤16

思路是状压 但我标程看不懂QAQ求大佬解释

#include <cstdio>
using namespace std;
typedef long long ll;
inline int abss(int x){return x<0?-x:x;}
int n,K,a[16];
ll res(0),f[1<<16][16];//f[i][j]表示状态为i,选了前j个数的情况数 这是我唯一看懂的一点QAQ
int main(){
    scanf("%d%d",&n,&K);
    for(int i=0;i<n;++i){
        scanf("%d",a+i);
        f[1<<i][i]=1;
    }
    for(int i=1;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                for(int k=0;k<n;++k)
                    if(j!=k && (i&(1<<k)) && abss(a[j]-a[k])>K)
                        f[i][j]+=f[i^(1<<j)][k];
    for(int i=0;i<n;++i)
        res+=f[(1<<n)-1][i];
    printf("%lld\n",res);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
2020/9/10 20:34
加载中...