AtCoder Beginner Contest 146 F問題 - Sugoroku

Source

AtCoder Beginner Contest 146
問題文

問題概要

省略

解法

省略

cLay（version 20191123-1）のコード

C++に変換後のコードはこちら

int N, M;
char S[100003];
int dp[100001], bk[100001];
int ress, res[100001];
{
  pair<int,int> p;
  segtree_Point_Min<int> t;
  rd(N,M,S);
  t.malloc(N+1,1);
  dp[0] = 0;
  rep(i,N){
    dp[i+1] = int_inf;
    if(S[i+1]=='0'){
      p = t.getMin(max(0,i+1-M), i+1);
      dp[i+1] <?= p.first + 1;
      bk[i+1] = p.second;
    }
    t.change(i+1,dp[i+1]);
  }
  if(dp[N]==int_inf) wt(-1), return 0;
  ress = dp[N];
  while(N){
    res[dp[N]-1] = N - bk[N];
    N = bk[N];
  }
  wt(res(ress));
}

Current time: 2024年04月27日02時40分30秒
Last modified: 2019年11月25日10時53分11秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC146 ABC_F
トップページに戻る

Logged in as: unknown user (not login)