24 544984352
一开始,尽力想了,但是发现不会递推
然后看了题解,才秒懂。。。只能说太抽象了,
但又感觉很实际,就是一定得找到最后的要求是什么,需要什么。
第 i 天有多少种方案。
令dp[i] 为第i天有多少种不同方案。
跟第i – 1 天有关,如果第i 天是 1 ,如果第i-1天是0,或者2肯定可以满足条件
如果第i-1天是1,由不能连续三天是同一个数字,所以i – 2天一定得是0或者2.
得到状态转移方程:
dp[i – 1] 为 第i-1天有多少种不同方案,那第i天选择1 或者 2 或者 3 就有不同情况了
然后构成状态转移方程式,参考分类计数原理和分步计数原理。
dp[i] = dp[i-1] * 2 + dp[i-2] * 2;
//————————-代码—————————-
#define int LL
const int N = 1e6+10;
int n,m;
int p[N];
int inf = 1e9+7;
void solve()
{
cin>>n;
// V<V<int>>mp(n+1,V<int>(m+1));
cout<<p[n]<<endl;
}
void pre() {
p[1] = 3;
p[2] = 9;
fo(i,3,100000) {
p[i] = 2 * (p[i-1] + p[i-2] + inf) % inf;
}
}
signed main(){
clapping();TLE;
pre();
int t;cin>>t;while(t — )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//————————————————————
声明:
本站所有资源文章出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。
本站资源均为网友投稿提供,本站展示资源说明和类型,本站不售卖资源,不盈利。
联系方式(#替换成@):21foxamerica#gmail.com
如果地址失效请及时留言补充资源
本站所有资源文章出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。
本站资源均为网友投稿提供,本站展示资源说明和类型,本站不售卖资源,不盈利。
联系方式(#替换成@):21foxamerica#gmail.com
如果地址失效请及时留言补充资源