求助!样例过了,全WA
查看原帖
求助!样例过了,全WA
377842
liuxy1234楼主2022/5/2 09:01
#include <bits/stdc++.h>
#define int  long long
using namespace std;

int f[11][83][1025], ans;

signed main()
{
	int n, k;
	cin >> n >> k;
	int ni = pow(2, n - 1);
	for(int i = 0;i <= ni - 1;i++)
	{
		if(i & (i << 1) || i & (i >> 1))continue;
		int a = i;
		int cnt = 0;
		while(a)
		{
			cnt += a & 1;
			a >>= 1;
		}
		f[1][cnt][i] = 1;
	}
	for(int i = 2;i <= n;i++)
	{
		for(int s = 0;s <= ni - 1;s++)
		{
			for(int t = 0;t <= ni - 1;t++)
			{
				if(s & t || s & (t << 1) || s & (t >> 1))continue;
				if(s & (s << 1) || s & (s >> 1))continue;
				int a = s;
				int cnt1 = 0;
				while(a)
				{
					cnt1 += a % 2;
					a >>= 1;
				}
				a = t;
				int cnt2 = 0;
				while(a)
				{
					cnt2 += a % 2;
					a >>= 1;
				}
				if(cnt2 + cnt1 > k)continue;
				for(int l = 0;l <= k - cnt1 - cnt2;l++)
					f[i][cnt2 + cnt1 + l][s] += f[i - 1][cnt2 + l][t];
			}
			for(int l = 0;l <= k;l++)
				ans += f[i][l][s];
		}
	}
	/*
	for(int i = 1;i <= n;i++)
	{
		for(int j = 0;j <= ni - 1;j++)
		{
			for(int l = 0;l <= k;l++)
			{
				cout << f[i][l][j] << " ";
			}
			cout << "\n"; 
		}
		cout << "\n";
	}
	*/
	cout << ans;
	return 0;
}

2022/5/2 09:01
加载中...