首页 > 代码库 > [HNOI2002] 公交车路线

[HNOI2002] 公交车路线

题目背景

在长沙城新建的环城公路上一共有8个公交站,分别为A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行,因此你从某一个公交站到另外一个公交站往往要换几次车,例如从公交站A到公交站D,你就至少需要换3次车。

技术分享

 

 

Tiger的方向感极其糟糕,我们知道从公交站A到公交E只需要换4次车就可以到达,可是tiger却总共换了n次车,注意tiger一旦到达公交站E,他不会愚蠢到再去换车。现在希望你计算一下tiger有多少种可能的乘车方案。

题目描述

输入输出格式

输入格式:

 

仅有一个正整数n(4<=n<=10000000),表示tiger从公交车站A到公交车站E共换了n次车。

 

输出格式:

 

仅有一个正整数,由于方案数很大,请输出方案数除以 1000后的余数。

 

输入输出样例

输入样例#1:
6
输出样例#1:
8

说明

8条路线分别是:

(A→B→C→D→C→D→E),(A→B→C→B→C→D→E),

(A→B→A→B→C→D→E),(A→H→A→B→C→D→E),

(A→H→G→F→G→F→E),(A→H→G→H→G→F→E),

(A→H→A→H→G→F→E),(A→B→A→H→G→F→E)。

 

题解:

看到数据范围n<=10000000。想到肯定要O(n)才能过。

O(n)算法复杂度+一个输入输出,肯定就是递推啦

可是递推公式??

暴力算前几个答案是

4  5  6  7  8  9  10  11  12  13  14

2  0  8  0  28    0  96  0  328  0  1120

发现当n为奇数时,ans=0;

开始想递推式

设f[i]=x*f[i-1]+y;           解出答案后代入后面是不成立的

设f[i]=x*f[i-1]+y*f[i-2]+z;

28=8x+2y+z;  96=28x+8y+z;    328=96x+28y+z;

解得 x=4;y=-2;z=0;带入后面也是成立的

于是,递推式就出来了,f[i]=4*f[i-1]-2*f[i-2];

一个非常坑的地方:由于答案%1000后f[i-2]有可能大于f[i-1]

所以极端情况下,f[i-2]=999,f[i-1]=0;所以如代码所示,还要+2000后再%1000

#include<iostream>
using namespace std;
int f[10000010];
int main()
{
int n;cin>>n;
if(n&1)cout<<0;
else
{
f[4]=2;f[6]=8;
for(int i=8;i<=n;i+=2)f[i]=(4*f[i-2]-2*f[i-4]+2000)%1000;
cout<<f[n];
}
return 0;
}

代码居然才写了15行。。。这是省选题啊

[HNOI2002] 公交车路线