记录编号	430862	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	hunter	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2017-07-30 19:03:36	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,ans,h;
int a[25],now[25],col[26];
void del(int x,int y,int z)
{
     for(int i=x;i<=y;i++) now[i]-=z;
}
void add(int x,int y,int z)
{
     for(int i=x;i<=y;i++) now[i]+=z;
}
int special()
{
    int op1=0,op2=0,op3=0,op4=0;
    for(int i=2;i<=16;i++)
    {
      if(now[i]==4) op4++;
      if(now[i]==3) op3++;
      if(now[i]==2) op2++;
      if(now[i]==1) op1++;
    }
  //  if(h==51) cout<<op1<<" "<<op2<<" "<<op3<<" "<<op4<<endl; 
    int num=0;
    while(op4&&op1>=2) {op4--;num++;op1-=2;}
    while(op4&&op2>=2) {op4--;num++;op2-=2;}
    while(op3&&op1>=1) {op3--;num++;op1-=1;}
    while(op3&&op2>=1) {op3--;num++;op2-=1;}
    num=num+op1+op2+op3+op4;
    
    return num; 
}
void dfs(int x)
{
     if(x>=ans) return ; 
     ans=min(ans,special()+x-1);
     for(int i=3;i<=14;i++)
     {
         int t=i,js=0;
         while(now[t]!=0&&t<=14) {js++;t+=1;}
         while(js>=5)
         {
             del(i,i+js-1,1);
             dfs(x+1);
             add(i,i+js-1,1);
             js--;     
         }    
     }
     for(int i=3;i<=14;i++)
     {
           int t=i,js=0;
           while(now[t]>=2&&t<=14) {js++;t+=1;}
           while(js>=3) 
           {
               del(i,i+js-1,2);
               dfs(x+1);
               add(i,i+js-1,2);
               js--;      
           }   
     }
     for(int i=3;i<=14;i++)
     {
          int t=i,js=0;
          while(now[t]>=3&&t<=14) {js++;t+=1;}
          while(js>=2) 
          {
               del(i,i+js-1,3);
               dfs(x+1);
               add(i,i+js-1,3); 
               js--;    
          }   
     }
     return ;
}
int main()
{
    freopen("landlords.in","r",stdin);
    freopen("landlords.out","w",stdout);
    scanf("%d%d",&T,&n);
    int ai,bi;
    for(h=1;h<=T;h++)
    {
        memset(a,0,sizeof(a));
        memset(now,0,sizeof(now));
        memset(col,0,sizeof(col));
        ans=n;
        for(int i=1;i<=n;i++)
        {
              scanf("%d%d",&ai,&bi);  
              if(ai==0) col[i]=16;
              else if(ai==1) col[i]=14;
              else col[i]=ai;
              a[col[i]]++;
        } 
        for(int i=1;i<=16;i++) now[i]=a[i];
        dfs(1);
        printf("%d\n",ans);   
    }
   // while(1);
    return 0;
}