超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC017D解いてみた

ABC017Dを解いてみました。
しゃくとり法+dpみたいなのは初めてで勉強になった。あと、dpを直接配列にしないで関数にしてやると初期条件で楽できるということに気づいた

#include <cstdio>
#include <algorithm>
#include <cstring>

#define MOD (1000*1000*1000 + 7)

using namespace std;

long long asMOD(long long var) {
  return ((var%MOD) + MOD) % MOD;
}

int f[100*1000+10];
long long _dp[100*1000+10];
int N,M;
bool used[100*1000+10];
long long dp(int n) {
  if (n==-1) {
    return 1;
  }
  if (n==-2) {
    return 0;
  }
  return _dp[n];
}
void setDp(int n,long long v) {
  _dp[n] = v;
}
int main() {
  memset(_dp, 0, sizeof(_dp));
  memset(used, 0, sizeof(used));
  scanf("%d%d", &N, &M);
  for(int i=0;i<N;++i) {
    scanf("%d", &f[i]);
  }

  for(int i=0,j=0;i<N;++i) {
    while(used[f[i]]) {
      used[f[j]]=false;
      j++;
    }
    used[f[i]] = true;
    setDp(i, asMOD(dp(i-1) + asMOD(dp(i - 1) - dp(j - 2))));
  }
  printf("%lld\n", asMOD(dp(N-1)-dp(N-2)));

  return 0;
}