题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3139
记忆化搜索。用map来存当前点的状态。然后搜索顺序要从大到小搜。
#include<cstring> #include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<map> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define inf int(1e9) #define maxn 15 #define mm 1000000007 #define ll long long using namespace std; map<ll,ll >mp; int a[maxn],tmp[maxn]; ll ans; int n; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } ll hash(int n){ rep(i,1,n) tmp[i]=a[i]; rep(i,1,n) rep(j,1,i) if (tmp[i]>tmp[j]) swap(tmp[i],tmp[j]); ll res=n; rep(i,1,n) res+=res*28+tmp[i]%mm; return res; } ll dfs(int o,int now){ if (a[now]>(now-o)*3) return -1; if (o==now){ if (now==1) return 1; else { ll h=hash(now-1); if (mp[h]) return mp[h]; else return mp[h]=dfs(1,now-1); } } ll res=0,tmp; if (a[o]>=3){ a[o]-=3; tmp=dfs(o+1,now); if (tmp!=-1) {res+=tmp; if (res>mm) res-=mm;} a[o]+=3; } if (a[o]&&a[now]) { a[now]--; a[o]--; tmp=dfs(o+1,now); if (tmp!=-1) {res+=tmp; if (res>mm) res-=mm;} a[o]++; a[now]++; } if (a[now]>=3){ a[now]-=3; tmp=dfs(o+1,now); if (tmp!=-1) {res+=tmp; if (res>mm) res-=mm;} a[now]+=3; } if (!res) return -1; return res; } int main(){ n=read(); rep(i,1,n) a[i]=read(); rep(i,1,n) rep(j,1,i) if (a[i]>a[j]) swap(a[i],a[j]); ans=dfs(1,n); printf("%lld ",ans); return 0; }