首页 > 代码库 > cdoj1587 失恋772002天

cdoj1587 失恋772002天

地址:http://acm.uestc.edu.cn/#/problem/show/1587

题目:

失恋772002天

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
 

日天失恋了,为了安慰他,锅爷决定带他去抓娃娃。锅爷买了111个币,连抓108把却一无所获。锅爷说:“这个娃娃机很邪”,于是把剩下3个币给了日天。日天仅用33把,就抓获一只海绵宝宝、一只卡布达和一只美羊羊。于是,他决定每天晚上和一只娃娃睡觉,来获取心灵上的慰藉。但是,日天是个有原则的人,他决不允许自己连续三天和三个不同的人睡觉,娃娃也是如此。请你来计算,按照日天的要求,他失恋的前NN天,共有多少种不同的睡觉方式呢?

Input

一个整数N(1N772002)N(1≤N≤772002),代表日天的失恋天数。

Output

输出日天失恋前N天的睡觉方案数对UESTC?ACM?2017UESTC?ACM?2017新人交流群群号:554056561取模的结果。

Sample input and output

Sample InputSample Output
1
3
2
9
3
21

思路:简单dp题

  dp方程见代码

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define MP make_pair
 6 #define PB push_back
 7 typedef long long LL;
 8 typedef pair<int,int> PII;
 9 const double eps=1e-8;
10 const double pi=acos(-1.0);
11 const int K=1e6+7;
12 const int mod=554056561;
13 
14 
15 int dp[K][2];
16 int main(void)
17 {
18     std::ios::sync_with_stdio(false);
19     std::cin.tie(0);
20     dp[1][0]=3;
21     dp[2][0]=3,dp[2][1]=6;
22     for(int i=3;i<=772002;i++)
23         dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod,dp[i][1]=(dp[i-1][0]*2+dp[i-1][1])%mod;
24     int x;
25     cin>>x;
26     cout<<(dp[x][0]+dp[x][1])%mod<<endl;
27     return 0;
28 }

 

cdoj1587 失恋772002天