舔狗舔到最后一无所有
2022/8/12 23:29:03
本文主要是介绍舔狗舔到最后一无所有,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LINK:舔狗舔到最后一无所有
参考题解
不能连续三天相等,而每一次又有三种选择。设f[i][j] (j=0/1/2)为第j天选择第i 种的方案总数。
- 如果第j天去了2,j-1天也去了2,那么第j-2 天去0 或1 才能满足条件.
- 如果第j天去了2,j-1天去了0 或 1,就可以满足条件了(因此与j-2无关)
-
f[0][i]=f[1][i-1]+f[2][i-1]+f[1][i-2]+f[2][i-2]
f[1][i]=f[0][i-1]+f[2][i-1]+f[0][i-2]+f[2][i-2]
f[2][i]=f[1][i-1]+f[0][i-1]+f[1][i-2]+f[0][i-2]
- 我们发现第i天去哪一家都是一样的,3家关系是相同的,因此可以缩小至一维
f[i]=f[i-1]*2+f[i-2]*2
-
#include <bits/stdc++.h> #define size 100100 const int MOD=1e9+7; using namespace std; long long dp[size],n,m; int main(){ dp[1]=3,dp[2]=9; for (int i=3;i<size;i++){ dp[i]=(dp[i-1]*2%MOD+dp[i-2]*2%MOD)%MOD; } scanf("%lld",&m); while (m--){ scanf("%lld",&n); printf("%lld\n",dp[n]); } system("pause"); return 0; }
这篇关于舔狗舔到最后一无所有的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署