NOIp 2015 Day1T3斗地主【搜索】

题目传送门

昨天真题测试赛题目==

没想到一道纯到都不用剪枝的搜索会是noipT3难度。

不过因为我搜索弱啊所以打不出来==

LA:这不就是一道简单模拟题么

码完此题能增加对搜索的理解==

（闲话结束）

搜索，我们就是要遍历每一个可能的状态，来寻取最优解。每次我们尝试取到一个状态，然后递归回溯，之后恢复原来的状态。

具体的搜索过程，我们可以贪心地每次先打出耗费牌数更多的手牌，最后对特殊的小王大王情况和单牌对牌进行处理。

  1 #include<algorithm>
  2 #include<cstdio>
  3 #include<cstring>
  4 
  5 using namespace std;
  6 
  7 int T,n,no,x,ans=19260817;
  8 int tong[20];
  9 
 10 void dfs(int now)
 11 {
 12     int cnt=0;
 13     for(int i=3;i<=14;i++)
 14     {// shunzi single
 15         if(tong[i]) cnt++;
 16         else cnt=0;
 17         if(cnt>=5)
 18         {
 19             tong[i]--,tong[i-1]--,tong[i-2]--,tong[i-3]--;
 20             int k=i-cnt+1;
 21             for(int j=i-4;j>=k;j--)
 22                 tong[j]--,dfs(now+1);
 23             for(int j=k;j<=i;j++)
 24                 tong[j]++;
 25         } 
 26     }
 27     cnt=0;
 28     for(int i=3;i<=14;i++)
 29     {// shunzi double
 30         if(tong[i]>=2) cnt++;
 31         else cnt=0;
 32         if(cnt>=3)
 33         {
 34             tong[i]-=2,tong[i-1]-=2;
 35             int k=i-cnt+1;
 36             for(int j=i-2;j>=k;j--)
 37                 tong[j]-=2,dfs(now+1);
 38             for(int j=k;j<=i;j++)
 39                 tong[j]+=2;
 40         }
 41     }
 42     cnt=0;
 43     for(int i=3;i<=14;i++)
 44     {// shunzi third
 45         if(tong[i]>=3) cnt++;
 46         else cnt=0;
 47         if(cnt>=2)
 48         {
 49             tong[i]-=3;
 50             int k=i-cnt+1;
 51             for(int j=i-1;j>=k;j--)
 52                 tong[j]-=3,dfs(now+1);
 53             for(int j=k;j<=i;j++)
 54                 tong[j]+=3;
 55         }
 56     }
 57     for(int i=3;i<=15;i++)
 58     {// four with 2
 59         if(tong[i]>=4)
 60         {
 61             tong[i]-=4;
 62             for(int j=3;j<=16;j++)
 63                 if(tong[j])
 64                 {//2 single
 65                     tong[j]--;
 66                     for(int k=3;k<=16;k++)
 67                         if(tong[k])
 68                         {
 69                             tong[k]--;
 70                             dfs(now+1);
 71                             tong[k]++;
 72                         }
 73                     tong[j]++;
 74                 }
 75             for(int j=3;j<=15;j++)
 76                 if(tong[j]>=2)
 77                 {//2 double
 78                     tong[j]-=2;
 79                     for(int k=3;k<=15;k++)
 80                         if(tong[k]>=2)
 81                         {
 82                             tong[k]-=2;
 83                             dfs(now+1);
 84                             tong[k]+=2;
 85                         }
 86                     tong[j]+=2;
 87                 }
 88             dfs(now+1);
 89             //three card
 90             tong[i]+=4;
 91         }
 92     }
 93     for(int i=3;i<=15;i++)
 94     {
 95         if(tong[i]>=3)
 96         {
 97             tong[i]-=3;
 98             for(int j=3;j<=16;j++)
 99                 if(tong[j])
100                 {//three with 1
101                     tong[j]--;
102                     dfs(now+1);
103                     tong[j]++; 
104                 }
105             for(int j=3;j<=15;j++)
106                 if(tong[j]>=2)
107                 {//three with 2
108                     tong[j]-=2;
109                     dfs(now+1);
110                     tong[j]+=2;
111                 }
112             dfs(now+1);// 3 single
113             tong[i]+=3;
114         }
115     }
116     if(tong[16]==2) now++;
117     else if(tong[16]==1) now++;
118     for(int i=3;i<=15;i++) if(tong[i]) now+=tong[i]>>1;
119     for(int i=3;i<=15;i++) if(tong[i]) now+=tong[i]&1;
120     ans=min(ans,now);
121 }
122 
123 int main()
124 {
125     scanf("%d%d",&T,&n);
126     while(T--)
127     {
128         for(int i=1;i<=n;i++)
129         {
130             scanf("%d%d",&x,&no);
131             if(x==1) x=14;
132             else if(x==2) x=15;
133             else if(x==0) x=16;
134             tong[x]++;
135         }
136         dfs(0);
137         printf("%d
",ans);
138         ans=19260817;
139         memset(tong,0,sizeof(tong));
140     }
141     return 0;
142 }

无注释版

  1 #include<algorithm>
  2 #include<cstdio>
  3 #include<cstring>
  4 
  5 using namespace std;
  6 
  7 int T,n,no,x,ans=19260817;
  8 int tong[20];
  9 
 10 void dfs(int now)
 11 {
 12     int cnt=0;
 13     for(int i=3;i<=14;i++)
 14     {// shunzi single
 15         if(tong[i]) cnt++;
 16         else cnt=0;
 17         if(cnt>=5)
 18         {
 19             tong[i]--,tong[i-1]--,tong[i-2]--,tong[i-3]--;
 20             int k=i-cnt+1;// 顺子牌还要枚举找到起点 
 21             for(int j=i-4;j>=k;j--)
 22                 tong[j]--,dfs(now+1);
 23             for(int j=k;j<=i;j++)
 24                 tong[j]++;
 25         } 
 26     }
 27     cnt=0;
 28     for(int i=3;i<=14;i++)
 29     {// shunzi double
 30         if(tong[i]>=2) cnt++;
 31         else cnt=0;
 32         if(cnt>=3)
 33         {
 34             tong[i]-=2,tong[i-1]-=2;
 35             int k=i-cnt+1;
 36             for(int j=i-2;j>=k;j--)
 37                 tong[j]-=2,dfs(now+1);
 38             for(int j=k;j<=i;j++)
 39                 tong[j]+=2;
 40         }
 41     }
 42     cnt=0;
 43     for(int i=3;i<=14;i++)
 44     {// shunzi third
 45         if(tong[i]>=3) cnt++;
 46         else cnt=0;
 47         if(cnt>=2)
 48         {
 49             tong[i]-=3;
 50             int k=i-cnt+1;
 51             for(int j=i-1;j>=k;j--)
 52                 tong[j]-=3,dfs(now+1);
 53             for(int j=k;j<=i;j++)
 54                 tong[j]+=3;
 55         }
 56     }
 57     for(int i=3;i<=15;i++)
 58     {// four with 2
 59         if(tong[i]>=4)
 60         {
 61             tong[i]-=4;
 62             for(int j=3;j<=16;j++)
 63                 if(tong[j])
 64                 {//2 single
 65                     tong[j]--;
 66                     for(int k=3;k<=16;k++)
 67                         if(tong[k])
 68                         {
 69                             tong[k]--;
 70                             dfs(now+1);
 71                             tong[k]++;
 72                         }
 73                     tong[j]++;//状态的恢复都是对称的 
 74                 }
 75             for(int j=3;j<=15;j++)
 76                 if(tong[j]>=2)
 77                 {//2 double
 78                     tong[j]-=2;
 79                     for(int k=3;k<=15;k++)
 80                         if(tong[k]>=2)
 81                         {
 82                             tong[k]-=2;
 83                             dfs(now+1);
 84                             tong[k]+=2;
 85                         }
 86                     tong[j]+=2;
 87                 }
 88             dfs(now+1);
 89             //three card
 90             tong[i]+=4;
 91         }
 92     }
 93     for(int i=3;i<=15;i++)
 94     {
 95         if(tong[i]>=3)
 96         {
 97             tong[i]-=3;
 98             for(int j=3;j<=16;j++)
 99                 if(tong[j])
100                 {//three with 1
101                     tong[j]--;
102                     dfs(now+1);
103                     tong[j]++; 
104                 }
105             for(int j=3;j<=15;j++)
106                 if(tong[j]>=2)
107                 {//three with 2
108                     tong[j]-=2;
109                     dfs(now+1);
110                     tong[j]+=2;
111                 }
112             dfs(now+1);// 3 single
113             tong[i]+=3;
114         }
115     }
116     if(tong[16]==2) now++;
117     else if(tong[16]==1) now++;
118     for(int i=3;i<=15;i++) if(tong[i]) now+=tong[i]>>1;//出对子牌 
119     for(int i=3;i<=15;i++) if(tong[i]) now+=tong[i]&1;//出单张牌 两者用位运算简化 
120     ans=min(ans,now);//更新答案 
121 }
122 
123 int main()
124 {
125     scanf("%d%d",&T,&n);
126     while(T--)
127     {
128         for(int i=1;i<=n;i++)
129         {
130             scanf("%d%d",&x,&no);
131             if(x==1) x=14;
132             else if(x==2) x=15;
133             else if(x==0) x=16;
134             tong[x]++;
135         }
136         dfs(0);//现在已经出了0张牌 
137         printf("%d
",ans);
138         ans=19260817;
139         memset(tong,0,sizeof(tong));
140     }
141     return 0;
142 }

有注释版