1 条题解
-
1
# include <bits/stdc++.h> # define int long long using namespace std; const int N=1e3+5; const int INF=0x3f3f3f3f; int n,k,ans; int state[N],len; int num[N]; int dp[10][1000][100]; int getNum(int x){ int sum=0; while(x){ sum++; x-=(x&-x); } return sum; } void init(){ for(int i = 0;i<(1<<n);i++){ if(!(i&(i<<1))){ state[++len]=i; num[len]=getNum(i); dp[1][len][num[len]]=1; } } } signed main(){ cin>>n>>k; init();; for(int i = 2;i<=n;i++){ for(int j = 1;j<=len;j++){ for(int l = 1;l<=len;l++){ int x=state[j],y=state[l]; if((x&y)||(x&(y<<1))||(x&(y>>1)))continue; for(int z = 0;z<=k-num[j];z++){ dp[i][j][z+num[j]]+=dp[i-1][l][z]; } } } } for(int i = 1;i<=len;i++) ans+=dp[n][i][k]; cout<<ans; return 0; }
- 1
信息
- ID
- 3576
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 18
- 已通过
- 12
- 上传者