題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=3139

---

?

　　可以發現，答案之和得分的序列有關，而且和序列中每個元素的順序無關。考慮HASH所有的狀態，記憶化搜索即可。

　　(取模出問題+沒有判斷是否訪問，即答案為0的狀態有的可能已經訪問過了)調了一個多小時。

---

?

#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cstdlib> #include<cmath> #include<cstring> #include<map> using namespace std; #define maxn 12 #define llg long long #define md 1000000007 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); llg n,m;map<llg,llg>f;bool cmp(llg a,llg b){return a<b;}struct node {llg a[maxn],len;void px() {sort(a+1,a+len+1,cmp);}llg hash(){llg tot=len,x=1;for (llg i=1;i<=len;i++){tot*=28;tot+=x*a[i];}//cout<<tot<<endl;return tot;} };llg ss(node w,llg x,llg res,llg up); llg dfs(node e);llg ss(node w,llg x,llg res,llg up) {llg ans=0;if (x>up){if (res==0) ans=dfs(w);return ans;}if (res>=3){ans+=ss(w,x+1,res-3,up); ans%=md;}if (res>=1 && w.a[x]>=1){w.a[x]--;ans+=ss(w,x+1,res-1,up);ans%=md;w.a[x]++;}if (w.a[x]>=3){w.a[x]-=3;ans+=ss(w,x+1,res,up);ans%=md;w.a[x]+=3;}return ans%md; }llg dfs(node e) {e.px();llg val=e.hash();if (f[val]!=0) return max((llg)0,f[e.hash()]);node ne=e;for (llg i=1;i<e.len;i++) ne.a[i]=ne.a[i+1];ne.len=e.len-1; ne.a[e.len]=0;f[val]=ss(ne,1,e.a[1],e.len-1)%md;if (f[val]==0) f[val]=-1; // cout<<e.hash()<<endl;return max((llg)0,f[val]); }int main() {yyj("match");cin>>n;node w; w.len=n;memset(w.a,0,sizeof(w.a));for (llg i=1;i<=n;i++) scanf("%lld",&w.a[i]);w.px(); f[0]=1;dfs(w);cout<<max((llg)0,f[w.hash()]);return 0; }

?

轉載于:https://www.cnblogs.com/Dragon-Light/p/6407419.html

總結

以上是生活随笔為你收集整理的【BZOJ】3139: [Hnoi2013]比赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。