Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

CF14E 题解

posted on 2022-03-13 12:04:06 | under 题解 |

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

题意

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