题解 P1990 【覆盖墙壁】

Juvenile · 2019-07-16 14:24:21 · 题解

这是一道明显的递推题

1.样例为13，我们可以先从1开始算

得到：dp[1]=1,dp[2]=2,dp[3]=5,dp[4]=11;

2.（大雾） 这有什么卵用吗

如果不是一些十分明显的规律数列

那就 不用想了 开始瞎搞

经过一系列玄学操作

你就会惊奇的发现 咦？

dp[i]=dp[i-1]*2+dp[i-3]; 这个式子居然过了样例

这样的话，就放心的把它怼上去吧。。。

Code：

#include<bits/stdc++.h>
using namespace std;
int dp[1000009],n;
int main()
{
    dp[1]=1;
    dp[2]=2;
    dp[3]=5;
    scanf("%d",&n);
    for(int i=4;i<=n;i++)
    {
        dp[i]=(dp[i-1]*2)%10000+dp[i-3]%10000;
        dp[i]%=10000;
    }
    printf("%d\n",dp[n]);
    return 0;   
}

希望排版调过之后重审能过！！！谢谢管理员大大！！！