uva 10364

From Evernote:

10364

未寫1:使用DFS試試看 結論:TLE...

未寫2:排序在DFS，突然想到狀態壓縮，先不使用做做看

Input:

1

8

1 1 2 2 3 4 5 6

結論:Bitmask不會用，使用sort後的dfs AC

--

[sourcecode language="cpp" htmlscript="false"]

//============================================================================

// Name : Square.cpp

// Date : 2013 2013/1/27 上午11:33:33

// Author : GCA

//============================================================================

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <climits>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <cctype>

#include <utility>

using namespace std;

typedef long long ll;

typedef unsigned int uint;

#define Set(a,s) memset(a,s,sizeof(a))

#define Write(w) freopen(w,"w",stdout)

#define Read(r) freopen(r,"r",stdin)

#define Pln() printf("\n")

#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()

#define De(x)printf(#x"%d\n",x)

#define For(i,x)for(int i=0;i<x;i++)

#define CON(x,y) x##y

#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\

printf("%d ",dp[htx][hty]);}Pln();}

#define M 100005

#define PII pair<int,int>

#define PB push_back

#define oo INT_MAX

#define Set_oo 0x3f

#define Is_debug true

#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)

using namespace std;

int min3(int x,int y,int z){

int tmp=min(x,y);

return min(tmp,z);

}

int max3(int x,int y,int z){

int tmp=max(x,y);

return max(tmp,z);

}

int n,val,judge;

int x[35],sele[35];

int sit=0;

void dfs(int s,int nowval,int num,int depth){

// for(int i=0;i<n;i++)printf("%d ",sele[i]);

// printf("nv%d n%d",nowval,num);

// Pln();

if(nowval==val){

return ;

}

if(num>=4||judge){

judge=1;

return ;

}

if(depth==0){

int i=0;

for(i=0;i<n;i++)if(sele[i]==0)break;

sele[i]=1;

dfs(i,x[i],num,depth+1);

sele[i]=0;

}

else{

for(int i=s+1;i<n;i++){

if(judge)break;

if(sele[i]==0&&nowval+x[i]<=val){

sele[i]=1;

dfs(i,nowval+x[i],num,depth+1);

sele[i]=0;

}

}

}

}

int main() {

ios_base::sync_with_stdio(0);

int test;

while(~scanf("%d",&test)){

while(test--){

val=0;judge=0;

Set(sele,0);

scanf("%d",&n);

for(int i=0;i<n;i++){

scanf("%d",&x[i]);

val+=x[i];

}

sort(x,x+n);

sit=0;

dp[0]=0;

if(val%4)printf("no\n");

else{

val/=4;

dfs(0,0,0,0);

if(judge)printf("yes\n");

else printf("no\n");

}

}

}

}

[/sourcecode]