BZOJ3139/BZOJ1306 HNOI2013比赛/CQOI2009循环赛（搜索）-白红宇

BZOJ3139/BZOJ1306 HNOI2013比赛/CQOI2009循环赛（搜索）

阅读量：4918 次

发布时间：2019-06-11

本文共 1513 字，大约阅读时间需要 5 分钟。

　　搜索好难啊。

　　1.对于每个分数集合记忆化。

　　2.某人得分超过总分，剪枝。

　　3.某人之后全赢也无法达到总分，剪枝。

　　4.每有一场比赛分出胜负总分会多三分，而平局则会多两分。某人的分出胜负场次或平局场次超过该限制，剪枝。

　　面向代码编程直到除了变量名几乎都一模一样还是T。最后发现记忆化判断某个状态是否已经搜过的时候，写成f.find(x)==f.end()而不是!f[x]会快几倍。果然一直都没有学会map。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define P 1000000007#define N 11#define ll long longint n,s,a[N],b[N],lim1,lim2;map
            
              f;ll dfs(int k,int p){ if (k==n) return 1; if (a[k]>3*(n-p+1)) return 0; if (p>n) { ll h=0; for (int i=k+1;i<=n;i++) b[i]=a[i];sort(b+k+1,b+n+1); for (int i=k+1;i<=n;i++) h=h*30+b[i]; if (f.find(h)==f.end()) f[h]=dfs(k+1,k+2); return f[h]; } else { ll sum=0; if (a[k]>=3&&lim1) {a[k]-=3;lim1--;sum+=dfs(k,p+1);lim1++;a[k]+=3;} if (a[k]>0&&a[p]>0&&lim2) {a[k]--,a[p]--;lim2--;sum+=dfs(k,p+1);lim2++;a[k]++,a[p]++;} if (a[p]>=3&&lim1) {a[p]-=3;lim1--;sum+=dfs(k,p+1);lim1++;a[p]+=3;} return sum; }}int main(){#ifndef ONLINE_JUDGE freopen("bzoj3139.in","r",stdin); freopen("bzoj3139.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i<=n;i++) s+=a[i]=read(); sort(a+1,a+n+1);reverse(a+1,a+n+1); lim1=s-(n-1)*n,lim2=(s-3*(s-(n-1)*n))>>1; cout<

转载于:https://www.cnblogs.com/Gloid/p/9820692.html

你可能感兴趣的文章