Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int main(){
- int n;
- long long ans=0;
- scanf("%d",&n);
- long long dp[n+1][10];
- for(int j=0;j<=9;j++) dp[1][j]=1;
- for(int i=2;i<=n;i++){
- dp[i][1] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4];
- dp[i][2] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][5];
- dp[i][3] = dp[i-1][2] + dp[i-1][3] + dp[i-1][6];
- dp[i][4] = dp[i-1][1] + dp[i-1][4] + dp[i-1][5] + dp[i-1][7];
- dp[i][5] = dp[i-1][2] + dp[i-1][4] + dp[i-1][5] + dp[i-1][6] + dp[i-1][8];
- dp[i][6] = dp[i-1][3] + dp[i-1][5] + dp[i-1][6] + dp[i-1][9];
- dp[i][7] = dp[i-1][4] + dp[i-1][7] + dp[i-1][8];
- dp[i][8] = dp[i-1][5] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9] + dp[i-1][0];
- dp[i][9] = dp[i-1][6] + dp[i-1][8] + dp[i-1][9];
- dp[i][0] = dp[i-1][8] + dp[i-1][0];
- }
- for(int j=0;j<=9;j++){
- ans+=dp[n][j];
- }
- printf("%lld",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement