hdu 4277 USACO ORZ(dfs暴捜+hash)
2494 ワード
N個の木の棒があって、互いに組み合わせてつなぎ合わせて、何種類の異なっている三角形を構成することができます.
構想:c>=b>=aを仮定してCを列挙し,Cのdfsに列挙BのDFSをネストする.
構想:c>=b>=aを仮定してCを列挙し,Cのdfsに列挙BのDFSをネストする.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define mod 2000007
using namespace std;
int n;
int X[20];
bool vis[20];
int ans;
long long sum;
long long hash[mod];
bool ok(int b,int c)
{
int a=sum-b-c;
if(a+b>c && c>=b && b>=a)return true;
return false;
}
bool work(long long t)
{
int v=t%mod;
while(hash[v]!=t && hash[v]!=-1)//..... IF 。 。。。
v=(v+10)%mod;
if(hash[v]==-1)
{
hash[v]=t;
return true;
}
return false;
}
void dfsb(int pos,int c,int b)
{
//printf("c = %d b = %d
",c,b);
for(int i=pos;i<=n;i++)
{
if(vis[i])continue;
vis[i]=true;
b+=X[i];
if(ok(b,c))
{
//printf("c = %d,b = %d,a = %d
",c,b,sum-b-c);
int a=sum-b-c;
long long t=(long long)a+(long long)b*sum+(long long)c*sum*sum;
if(work(t))ans++;
}
if(b<=c)dfsb(i,c,b);
b-=X[i];
vis[i]=false;
}
}
void dfsc(int pos,int c)
{
for(int i=pos;i<=n;i++)
{
if(vis[i])continue;
vis[i]=true;
c+=X[i];
if(c>=sum/3 && c<=sum/2)dfsb(1,c,0);//
dfsc(i,c);
c-=X[i];
vis[i]=false;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(vis,0,sizeof(vis));
memset(hash,-1,sizeof(hash));
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&X[i]);
sum+=X[i];
}
ans=0;
dfsc(1,0);
printf("%d
",ans);
}
return 0;
}