HDU-4277(暴力プラス+hash)
2171 ワード
本テーマの裸暴力の複雑さは
sum = C(n,k)*2^K = (1 + 2)^N; 最大3^15は1 e 7程度で、明らかに暴力的に枝を切った問題がある.
では、三角形の制限条件に合わせてカットし、hashを加えるとすぐにできます.
sum = C(n,k)*2^K = (1 + 2)^N; 最大3^15は1 e 7程度で、明らかに暴力的に枝を切った問題がある.
では、三角形の制限条件に合わせてカットし、hashを加えるとすぐにできます.
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,x,y) for(int i=x;i<=(int)y;i++)
typedef long long ll;
typedef pair<int,int> pii;
const int N = 16;
const int mm = 1e5+7;
int vis[N],n,cnt,a[N],sum;
int cmp(int a,int b){
return a>b;
}
struct hashtable
{
int size,ans[mm][3],next[mm],h[mm];
int hash(int a,int b,int c){
return ((((a*131+b)*131+c)*131)&0x7FFFFFFF)%mm;
}
void insert(int a,int b,int c){
int ha = hash(a,b,c);
for(int i=h[ha]; i!=-1; i=next[i])
if(ans[i][0]==a && ans[i][1]== b && ans[i][2]== c) return;
ans[size][0]=a; ans[size][1]=b; ans[size][2]=c;
next[size]=h[ha];
h[ha]=size++;
}
void clear()
{
memset(h,-1,sizeof(h));
size=0;
}
} g;
void dfs2(int p,int fir,int val)
{
if(fir < val) return ;
if(p == n+1)
{
if(val < sum - val - fir) return ;
g.insert(fir,val,sum-val-fir);
return ;
}
if(!vis[p])
{
vis[p] = 1;
dfs2(p+1,fir,val+a[p]);
vis[p] = 0;
}
dfs2(p+1,fir,val);
}
void dfs(int p,int val)
{
if(p == n+1)
{
if(val < sum - val) dfs2(1,val,0);
return ;
}
vis[p] = 1;
dfs(p+1, val+a[p]);
vis[p] = 0;
dfs(p+1, val);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
g.clear();
memset(vis,0,sizeof(vis));
sum = 0;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]),sum+=a[i];
}
sort(a+1,a+1+n,cmp);
cnt=0;
dfs(1,0);
cout<<g.size<<endl;
}
return 0;
}