[DP 形状 线性]P1990 覆盖墙壁

[DP 形状 线性]P1990 覆盖墙壁

​​题目链接​​

思路

把边界形状作为状态标识，类似杨老师照相序列那题

为长度为i,状态为j的方案数

目标是：

代码

// Problem: P1990 覆盖墙壁
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1990
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// FishingRod

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY

*/
int T;
const int N=1E6+10;
LL f[N][4];
LL work(int n,int k)
{
  if(f[n][k]!=0)return f[n][k];
  if(n==2&&k==0)return 1;
  if(n==2&&k==1)return 1;
  if(n==2&&k==2)return 2;
  if(n==1&&k==2)return 1;
  if(k==0)
  {
    return f[n][k]=(work(n-1,1)+work(n-2,2))%10000;
  }
  else if(k==1)
  {
    return f[n][k]=(work(n-1,0)+work(n-2,2))%10000;
  }
  else
  {
    return f[n][k]=(work(n-1,0)+work(n-1,1)+work(n-1,2)+work(n-2,2))%10000;
  }
}
void solve(int C)
{
  //NEW DATA CLEAN
  
  //NOTE!!!
  LL n;cin>>n;
  cout<<work(n,2);
}

int main()
{
  #ifdef MULINPUT
    scanf("%d",&T);
    for(int i=1;i<=T;i++)solve(i);
  #else
    solve(1);
  #endif
  return 0;
}