大家好，又见面了，我是你们的朋友全栈君。
我讨厌dfs……题解不想写……自己看吧……->这里
//minamoto
#include<bits/stdc++.h>
#define ll unsigned long long
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
using namespace std;
const ll Base=37,P=1e9+7;const int N=1005;
int n,m,a[N],b[N],s[N],su,sx,sy;map<ll,ll>h;
inline bool cmp(const int &x,const int &y){return x>y;}
ll dfs(int u,int v){
ll res=0;if(u==n)return 1;if(a[u]+3*(n-v+1)<s[u])return 0;
if(v>n){
fp(i,u+1,n)b[i]=s[i]-a[i];sort(b+u+1,b+n+1);
ll S=0;fp(i,u+1,n)S=S*Base+b[i];
if(h.count(S))return h[S];
else return h[S]=dfs(u+1,u+2);
}
if(a[u]+3<=s[u]&&sx)a[u]+=3,--sx,res+=dfs(u,v+1),a[u]-=3,++sx;
if(a[u]+1<=s[u]&&a[v]+1<=s[v]&&sy)++a[u],++a[v],--sy,res+=dfs(u,v+1),--a[u],--a[v],++sy;
if(a[v]+3<=s[v]&&sx)a[v]+=3,--sx,res+=dfs(u,v+1),a[v]-=3,++sx;
return res%P;
}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d",&n);fp(i,1,n)scanf("%d",&s[i]),su+=s[i];
sx=su-n*n+n,sy=(su-3*sx)>>1;sort(s+1,s+1+n,cmp);
printf("%lld\n",dfs(1,2)%P);
}转载于:https://www.cnblogs.com/bztMinamoto/p/10041365.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107174.html原文链接：https://javaforall.net
