));
90 for(int l=12;l>=5;l--)
91 {
92 for(int i=1;i<=12-l+1;i++)
93 {
94 bool yx=1;
95 for(int j=i;j<=i+l-1;j++)
96 {
97 if(la[j]<1)
98 {
99 yx=0;
100 break;
101 }
102 }
103 if(yx)
104 {
105 memcpy(la,ll,sizeof(ll));
106 for(int j=i;j<=i+l-1;j++)
107 {
108 la[j]-=1;
109 }
110 dfs3(js+1);
111 memcpy(la,ll,sizeof(ll));
112 }
113 }
114 }
115 memcpy(la,ll,sizeof(ll));
116 dfs4(js,0);
117 }
118 void dfs2(int js){ //2s
119 if(js>=ans) return;
120 int ll[14];
121 memcpy(ll,la,sizeof(la));
122 for(int l=11;l>=3;l--)
123 {
124 for(int i=1;i<=12-l+1;i++)
125 {
126 bool yx=1;
127 for(int j=i;j<=i+l-1;j++)
128 {
129 if(la[j]<2)
130 {
131 yx=0;
132 break;
133 }
134 }
135 if(yx)
136 {
137 memcpy(la,ll,sizeof(ll));
138 for(int j=i;j<=i+l-1;j++)
139 {
140 la[j]-=2;
141 }
142 dfs2(js+1);
143 memcpy(la,ll,sizeof(ll));
144 }
145 }
146 }
147 memcpy(la,ll,sizeof(ll));
148 dfs3(js);
149 }
150 void dfs1(int js){ //3s
151 if(js>=ans) return;
152 int ll[14];
153 memcpy(ll,la,sizeof(la));
154 for(int l=7;l>=2;l--)
155 {
156 for(int i=1;i<=12-l+1;i++)
157 {
158 bool yx=1;
159 for(int j=i;j<=i+l-1;j++)
160 {
161 if(la[j]<3)
162 {
163 yx=0;
164 break;
165 }
166 }
167
168 if(yx)
169 {
170 memcpy(la,ll,sizeof(ll));
171 for(int j=i;j<=i+l-1;j++)
172 {
173 la[j]-=3;
174 }
175 dfs1(js+1);
176 memcpy(la,ll,sizeof(ll));
177 }
178 }
179 }
180 memcpy(la,ll,sizeof(ll));
181 dfs2(js);
182 }
183 int main(){
184 scanf("%d%d",&t,&n);
185 while(t--)
186 {
187 memset(sum,0,sizeof(sum));
188 memset(la,0,sizeof(la));
189 memset(num,0,sizeof(num));
190 ans=0x7fffffff;
191 int a,b,c,d;
192 for(int i=1;i<=n;i++)
193 {
194 int xx,yy;
195 scanf("%d%d",&xx,&yy);
196 if(xx==1)
197 xx=12;
198 else if(xx==2)
199 xx=13;
200 else xx-=2;
201 if(xx==-2) xx=0;
202 sum[xx]++;
203 }
204 memcpy(la,sum,sizeof(sum));
205 dfs1(0);
206 if(sum[0]) ans++;
207 printf("%d\n",ans);
208 }
209 //while(1);
210 return 0;
211 }
View Code
|