Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## DFS+剪枝 0ms水过

Posted by ACAccepted at 2019-02-10 18:22:19 on Problem 2362 and last updated at 2019-02-10 18:24:04
``````cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

{
int x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
return x*f;
}

const int MAXN=30;
int n,sum,len;
bool flag;
int stick[MAXN],nx[MAXN];
bool used[MAXN];

bool cmp(int a,int b)
{
return a>b;
}

int find(int l,int r,int weight)
{
int mid;
while (l<r)
{
mid=(l+r)>>1;
if (stick[mid]<=weight)r=mid;
else l=mid+1;
}
return l;
}

void dfs(int t,int rest,int last)
{
if (rest==0)
{
if (t==1)
{
flag=true;return ;
}
int x=0;
for (int i=1;i<=n;i++)
if (!used[x=i])break;
used[x]=true;
dfs(t-1,len-stick[x],x);
used[x]=false;
return ;
}
int l=find(last+1,n,rest);
for (int i=l;i<=n;i++)
{
if (!used[i])
{
used[i]=true;
dfs(t,rest-stick[i],i);
used[i]=false;
if (flag)return ;
if (rest==stick[i])return ;
i=nx[i];
if (i==n)return ;
}
}
}

int main()
{
while (cas--)
{
sum=0;flag=false;len=0;
memset(stick,0,sizeof(stick));
memset(nx,0,sizeof(nx));
for (int i=1;i<=n;i++)
{
sum+=stick[i];
}
sort(stick+1,stick+n+1,cmp);
nx[n]=n;
for (int i=n-1;i>=1;i--)
{
if (stick[i]==stick[i+1])nx[i]=nx[i+1];
else nx[i]=i;
}
if (sum%4==0 && stick[1]<=sum/4)
{
len=sum/4;
used[1]=true;
dfs(4,len-stick[1],1);
used[1]=false;
}
if (flag)puts("yes");
else puts("no");
}
return 0;
}
``````

Followed by: