[关闭]
@ysner 2018-07-25T09:07:14.000000Z 字数 1656 阅读 1660

[HNOI2013]比赛

搜索 记忆化


题面

个球队,两两比赛,胜得分,平各得分。告知每队最后得分,询问有多少种不同比赛结果。

解析

很有深意啊。反正这题不可能状压,那肯定是叫我们打记搜。

我一开始的想法是把搜索的状态设为各组当时的得分(爆不了)。
然而这样就不能记忆化了,因处理(
)得分时不知道两个队是否比赛过,强设该状态又炸空间。

于是还是枚举每场比赛的结果吧。
当然,可以有剪枝:

还有值得注意的一点,数组初始值应该设为,这样才能同已经计算过、方案数为的情况区分开来

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<map>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7;
  17. map<ll,ll>dp;
  18. ll n,pj,a[20];
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il bool cmp(re ll x,re ll y){return x>y;}
  29. il ll calc(re int x)
  30. {
  31. re ll New=x,d[20];//!!!!
  32. fp(i,1,x) d[i]=a[i];
  33. sort(d+1,d+1+x);//!!!!!
  34. fp(i,1,x) New=New*28+d[i];//!!!!
  35. return New;
  36. }
  37. il ll dfs(re int l,re int r)
  38. {
  39. re ll tot=0;
  40. if(a[r]>3*(r-l)) return -1;
  41. if(l==r)
  42. if(r==1) return 1;
  43. else
  44. {
  45. re ll now=calc(r-1);
  46. if(dp[now]) return dp[now];
  47. else return dp[now]=dfs(1,r-1);
  48. }
  49. if(a[l]>=3)
  50. {
  51. a[l]-=3;
  52. re ll tmp=dfs(l+1,r);if(tmp!=-1) tot+=tmp;if(tot>=mod) tot-=mod;
  53. a[l]+=3;
  54. }
  55. if(a[r]>=3)
  56. {
  57. a[r]-=3;
  58. re ll tmp=dfs(l+1,r);if(tmp!=-1) tot+=tmp;if(tot>=mod) tot-=mod;
  59. a[r]+=3;
  60. }
  61. if(a[l]&&a[r])
  62. {
  63. --a[l];--a[r];
  64. re ll tmp=dfs(l+1,r);if(tmp!=-1) tot+=tmp;if(tot>=mod) tot-=mod;
  65. ++a[l];++a[r];
  66. }
  67. return tot?tot:-1;
  68. }
  69. int main()
  70. {
  71. n=gi();
  72. fp(i,1,n) a[i]=gi();
  73. sort(a+1,a+1+n,cmp);
  74. printf("%lld\n",dfs(1,n));
  75. return 0;
  76. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注