90分求调,#7WA(递归搜索)
查看原帖
90分求调,#7WA(递归搜索)
1115386
dingxiangqian楼主2024/9/13 21:37
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
bool ans1;
int m,vis[50];
int sum=0;
bool ans[11];
int w[21];
bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int step,int a,int b,int c,int d)
{
    if(a>sum/4||b>sum/4||c>sum/4||d>sum/4)return;
    if(ans1)return;
    if(step==m+1)
    {
        if(a==b&&b==c&&c==d)ans1=true;
        return;
    }
    if(a+w[step]<=sum/4) dfs(step+1,a+w[step],b,c,d);
    if(b+w[step]<=sum/4) dfs(step+1,a,b+w[step],c,d);
    if(c+w[step]<=sum/4) dfs(step+1,a,b,c+w[step],d);
    if(d+w[step]<=sum/4) dfs(step+1,a,b,c,d+w[step]);
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	    cin>>m;
	    for(int j=1;j<=m;j++)
	    {
	        cin>>w[j];
	        sum+=w[j];
	    }
	    sort(w+1,w+n+1,cmp);
	    if(sum%4==0)
	    {
	        dfs(1,0,0,0,0);
	        ans[i]=ans1;
	        ans1=false;
	    }
	    sum=0;
	}
	for(int i=1;i<=n;i++)
	{
	    if(ans[i]==true)cout<<"yes\n";
	    else cout<<"no\n";
	}
    return 0;
}
2024/9/13 21:37
加载中...