可以加一个类似记忆化的数组,因为#25的数据长这样:
```
10 23
12 1
11 4
5 3
10 4
4 2
12 3
6 4
8 3
10 2
12 4
9 1
6 1
4 1
8 4
7 3
6 3
7 1
4 4
7 2
0 2
8 1
1 3
6 2
12 1
......
```
out
```
5
5
5
5
5
5
5
5
5
5
```
这是一模一样的10个数据,我加完数组就A了。
调整后代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int register int
#define ll long long
ll b[101][25],vis[101];
inline signed read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
ll pai[20];
ll ans=1e9;
void dfs(ll sum)
{
if(sum>=ans) return;
int k=0;
for(int i=3;i<=14;++i)//3s
{
if(pai[i]>=3)
{
++k;
if(k>=2)
{
for(int j=i;j>=i-k+1;--j) pai[j]-=3;
dfs(sum+1);
for(int j=i;j>=i-k+1;--j) pai[j]+=3;
}
}
else k=0;
}
k=0;
for(int i=3;i<=14;++i)//2s
{
if(pai[i]>=2)
{
++k;
if(k>=3)
{
for(int j=i;j>=i-k+1;--j) pai[j]-=2;
dfs(sum+1);
for(int j=i;j>=i-k+1;--j) pai[j]+=2;
}
}
else k=0;
}
k=0;
for(int i=3;i<=14;++i)//1s
{
if(pai[i]>=1)
{
++k;
if(k>=5)
{
for(int j=i;j>=i-k+1;--j) --pai[j];
dfs(sum+1);
for(int j=i;j>=i-k+1;--j) ++pai[j];
}
}
else k=0;
}
for(int i=2;i<=14;++i)//4
{
if(pai[i]>=4)
{
pai[i]-=4;//4+2
for(int j=2;j<=14;++j)//4+2+2
{
// if(i==j) continue;
if(pai[j]>=2)
{
pai[j]-=2;
for(int k=2;k<=14;++k)
{
if(pai[k]>=2)
{
pai[k]-=2;
dfs(sum+1);
pai[k]+=2;
}
}
pai[j]+=2;
}
}
for(int j=2;j<=16;++j)//4+1+1
{
// if(i==j) continue;
if(pai[j]>=1)
{
pai[j]--;
for(int k=2;k<=16;++k)
{
if(pai[k])
{
pai[k]--;
dfs(sum+1);
pai[k]++;
}
}
pai[j]++;
}
}
pai[i]+=4;
}
}
for(int i=2;i<=14;++i)//3+2
{
if(pai[i]==3)
{
pai[i]-=3;
for(int j=2;j<=14;++j)
{
// if(j==i) continue;
if(pai[j]>=2)
{
pai[j]-=2;
dfs(sum+1);
pai[j]+=2;
}
}
pai[i]+=3;
}
}
for(int i=2;i<=14;++i)//3+1
{
if(pai[i]==3)
{
pai[i]-=3;
for(int j=2;j<=16;++j)
{
// if(j==i) continue;
if(pai[j]>=1)
{
pai[j]-=1;
dfs(sum+1);
pai[j]+=1;
}
}
pai[i]+=3;
}
}
for(int i=2;i<=16;++i) if(pai[i]) ++sum;
if(pai[15]&&pai[16]) --sum;
ans=min(ans,sum);
}
signed main()
{
int T=read(),n=read();
int st=T;
while(T--)
{
for(int i=0;i<=19;++i) pai[i]=0;
for(int i=1;i<=n;++i)
{
int temp=read(),c=read();
if(temp==1) temp=14;
if(!temp) temp=14+c;
++pai[temp];
++b[temp][T+1];
}
int flag=0;
for(int i=st;i>T+1;i--)
{
bool y=true;
for(int j=1;j<=15;j++)
if(b[j][i]!=pai[j])
{
y=false;
break;
}
if(y)
{
flag=i;
break;
}
}
if(flag)
cout<<vis[flag]<<endl;
else
{
ans=0xfffffff;
dfs(0);
vis[T+1]=ans;
cout<<ans<<endl;
}
}
return 0;
}
```
by qiuqiuqzm @ 2023-07-16 16:21:32
@[H2O_TX](/user/228778)
by qiuqiuqzm @ 2023-07-19 16:57:42