捞(玄关)
查看原帖
捞(玄关)
827873
abc1856896楼主2024/5/20 09:07

50

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[1005] ;
int sum, k;
bool dfs(int x, int ah, int bh, int ch, int dh){
	if(x > n) {
		return (ah==bh && bh==ch && ch==dh && dh==k);
	}
	if(ah > k || bh > k || ch > k || dh > k) return false;
	if(dfs( x+1 ,ah + a[x], bh,  ch, dh)) return true;
	if(dfs( x+1 ,ah , bh + a[x], ch, dh)) return true;
	if(dfs( x+1 ,ah , bh, ch + a[x], dh)) return true;
	if(dfs( x+1 ,ah , bh, ch, dh + a[x])) return true;
}
void solve () {
	sum = 0, k = 0;
	memset ( a, 0, sizeof ( a));
	cin >> n;
	for ( int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	if ( sum % 4 != 0) {
		cout << "no\n";
		return;
	}
	k = sum / 4;
	sort ( a + 1, a + n + 1, greater<int>());
	if( dfs( 1, 0, 0, 0, 0)) cout << "yes\n";
	else cout << "no\n";
	return ;
}
signed main(){
	int T;
	cin >> T;
	while ( T--){
		solve ();
	} 
    return 0;
}
2024/5/20 09:07
加载中...