转载

[转载] $CF669A$ 题解

阅读原文

写在前面:
虽然\(CF\)的题目存在恶意评分现象,但是题目本身还是很有意义的,尤其是一题多解,能够很好地训练我们的思维啦~

观察题目条件,每次给个数,相邻的数不能一样,和为\(n\),要使次数最多。

由不一样可知,你不能一直填\(1\),又要次数最多,则\(1\)\(2\)应当交换着填。

对于每一个正整数,都可以像割肉一样一块一块地分割为\(1\)\(2\),这样才能保证次数最多。

那么,我们可以对每一个数采用搜索的方法来“割肉”,上次割掉\(1\)这次就割掉\(2\),直至剩下\(1\)\(2\)时再割一次即可。

对于输入为\(1\)\(2\)的情况,直接特判1次即可。(其实不特判也能过)

代码如下:

#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; }

如有疑问,评论区见,感谢资瓷!

转载于:https://www.cnblogs.com/Peter0701/p/11296100.html

正文到此结束
本文目录