CF14E 题解
Jerrlee✅
2022-03-13 12:04:06
**首先声明一下，这是一篇不正经的题解。**
## 题意
一行有 $n$ 个空位，每个空位可以填 $[1,4]$ 的整数，相邻两个数不相同，要求：
1. 有 $t$ 个位置满足 $a_{i-1}<a_i>a_{i+1}$ 且 ($1<i<n$)；
2. 有 $t-1$ 个位置满足 $a_{i-1}>a_i<a_{i+1}$。
范围：$1 \leq n \leq 20$，$1 \leq t \leq 10$。
## 思路
看到数据范围小，首先想到爆搜，但分支太多，还是会 T：<https://codeforces.com/contest/14/submission/149478428>
但既然有了暴力程序，数据范围这么小，我们可以想到什么？
**对啊，打表啊！**
对爆搜程序（假设大家都会，不进行讲解）进行修改，记得多测清空即可：
```cpp
#include<cstdio>
#include<cstring>
int n,t,ans,a[50];
void dfs(int x,int y,int z){
if(y>t||z>=t) return;
if(x==n+1){
if(y==t&&z==t-1) ans++;
return;
}
for(int i=1;i<=4;i++){
if(a[x-1]!=i){
a[x]=i;
if(x<3) dfs(x+1,y,z);
else{
if(a[x-2]<a[x-1]&&a[x-1]>i) dfs(x+1,y+1,z);
else if(a[x-2]>a[x-1]&&a[x-1]<i) dfs(x+1,y,z+1);
else dfs(x+1,y,z);
}
}
}
}
int main(){
for(int i=1;i<=20;i++){
for(int j=1;j<=10;j++){
n=i,t=j,ans=0;
memset(a,0,sizeof a);
dfs(1,0,0);
printf("if(n==%d&&t==%d) cout<<%d<<endl;\n",n,t,ans);
}
}
}
```
输出出来的就是表啦！
代码太长了，放剪贴板里了：<https://www.luogu.com.cn/paste/rt4w43t4>
[AC 记录（洛谷）](https://www.luogu.com.cn/record/71286874)
[AC 记录（CF）](https://codeforces.com/contest/14/submission/149478154)