CF669A 题解

写在前面： 虽然$CF$的题目存在恶意评分现象，但是题目本身还是很有意义的，尤其是一题多解，能够很好地训练我们的思维啦～ 观察题目条件，每次给个数，相邻的数不能一样，和为$n$，要使次数最多。 由不一样可知，你不能一直填$1$，又要次数最多，则$1$和$2$应当交换着填。 对于每一个正整数，都可以像割肉一样一块一块地分割为$1$和$2$，这样才能保证次数最多。 那么，我们可以对每一个数采用搜索的方法来“割肉”，上次割掉$1$这次就割掉$2$，直至剩下$1$或$2$时再割一次即可。 对于输入为$1$或$2$的情况，直接特判1次即可。（其实不特判也能过） 代码如下： ```cpp #include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n; int dfs(int n,int step,int mi) { if(n<=2) return step+1; if(n>2) { if(mi==1) dfs(n-1,step+1,2); else dfs(n-2,step+1,1); } } int main() { n=read(); if(n<=2) printf("1\n"); else printf("%d\n",dfs(n,0,1)); return 0; } ``` 如有疑问，评论区见，感谢资瓷！