2 条题解
-
1
#include <iostream> #include <cmath> #include <cstring> #include <string.h> #include <algorithm> #include <vector> using namespace std; const int N = 1e3 + 10; const int INF = 0x3f3f3f3f; long long dp[15][N][110],ans; int n,m,cnt; int a[N],sum[N]; int main(){ cin >> n >> m; for(int i=0; i<(1<<n); i++) { if(i & (i << 1) || i & (i >> 1))continue; a[++cnt] = i; int x = i; while(x) { sum[cnt] += x & 1; x >>= 1; } } for(int i = 1;i <= cnt; i++) dp[1][i][sum[i]]=1; for(int i = 2;i <= n; i++) { for(int j = 1;j <= cnt;j++) { for(int k = 1;k <= cnt;k++) { if(a[j]&a[k]||(a[j]>>1)&a[k]||(a[j]<<1)&a[k])continue; for(int l=sum[j]+sum[k];l<=m; l++) dp[i][j][l] += dp[i-1][k][l-sum[j]]; } } } for(int i=1; i<=cnt; i++) ans += dp[n][i][m]; cout << ans; return 0; }
信息
- ID
- 486
- 时间
- 500ms
- 内存
- 64MiB
- 难度
- 4
- 标签
- 递交数
- 36
- 已通过
- 20
- 上传者