大家好,又见面了,我是你们的朋友全栈君。
我讨厌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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107174.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...