2 条题解

  • 1
    @ 2023-8-9 15:11:17
    #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
    上传者