首先声明一下，这是一篇不正经的题解。

题意

一行有 $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

但既然有了暴力程序，数据范围这么小，我们可以想到什么？

对啊，打表啊！

对爆搜程序（假设大家都会，不进行讲解）进行修改，记得多测清空即可：

#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 记录（洛谷）

AC 记录（CF）