1147.Sam数

2024-01-30 09:08

文章标签 sam 1147

本文主要是介绍1147.Sam数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1147.Sam数

时间限制:1000MS内存限制:128000KB

题目描述

　　　小G最近发现了一种非常有趣的数，他将这种数称之为Sam数。Sam数具有以下特征：相邻两位的数字之差不超过2。小G还将Sam数按位数进行了分类，他将一个k位Sam数称之为k阶Sam数。但不幸的是小G发现他数不清第k阶的Sam数一共有多少个，这个时候机智的他想到了向你求助。

输入

第一行为一个整数k，含义见题面。

输出

一行一个整数ans，表示k阶的Sam数的个数。
由于第k阶Sam数非常多，你只需要输出ans mod 1,000,000,007。

输入样例复制

４

输出样例复制

867

说明

【数据规模和约定】对于30%的数据，1 ≤ k ≤ 6。对于60%的数据，1 ≤ k ≤ 1000。对于100%的数据，1 ≤ k ≤ 1000000。

题意：

在k位数中，满足相邻俩位之差不过2；例如，1234，可以

1357，可以，5357，可以、531-1，不行；

有一点很坑：k=1时，答案是10；

解法：

啧啧，似乎是DP，看到这一题我第一想法是打表，

先讲打表：

因为数30 percent 数据只有6位，所以说开另一个程序，用6个for枚举6位数得到结果，就在程序中直接输出。

简单易懂对不？

另一种DP：

f[i][k]=f[i][k]+f[i-1][j];

i表示i位数，k表示以K结尾。J是一个FOR，枚举能放在最后一位的数。

记住初值为１；

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

int n,m=1000000007,f[1000005][10],ans;
int main()
{

   cin>>n;
   if (n==1)
   {
       cout<<10;
       return 0;
   }
   for (int i=0;i<=9;i++) f[1][i]=1;
   for (int i=2;i<=n;i++)
   for (int j=0;j<=9;j++)
   for (int k=max(0,j-2);k<=min(9,j+2);k++)
   {
       f[i][j]=(long long)(f[i][j]+f[i-1][k])%m;
   }
   for (int i=1;i<=9;i++)
   {
       ans=(long long)(f[n][i]+ans)%m;
   }
cout<<ans;
}