AOJ 0517 Longest Steps

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0517
書いてあるような問題です。O(n)で求められます。

動的計画法みたいな感じで解きました。頑張ればO(klogk)ぐらいで解けるような気もします。
コーナーケースにも引っかからず一発ACだったので割と嬉しい。

int dp[100000][2];
int in[100000];

main(){
  int n,k;
  while(cin>>n>>k,n|k){
    memset(dp,0,sizeof(dp));
    memset(in,0,sizeof(in));
    int t;
    bool w=false;
    rep(i,k){
      cin>>t;
      if(!t)w=true;
      else dp[t-1][0]=dp[t-1][1]=in[t-1]=true;
    }
    
    int uans=1,ans=1;
    dp[0][1]=true;
    for(int i=1;i<n;i++){
      dp[i][1]=true;
      if(in[i-1] && in[i]){
	dp[i][0]=dp[i-1][0]+1;
	dp[i][1]=dp[i-1][1]+1;
      }
      if(in[i-1] && !in[i]){
	dp[i][0]=0;
	dp[i][1]=dp[i-1][0]+1;
      }
      
      if(!in[i-1] && in[i]){
	dp[i][0]=1;
	dp[i][1]=2;
	if(i>=2)dp[i][1]=dp[i-2][0]+2;
      }
      
      if(!in[i-1] && !in[i]){
	dp[i][0]=0;
	dp[i][1]=1;
      }
      ans=max(ans,dp[i][0]);
      uans=max(uans,dp[i][1]);
      //cout<<dp[i][0]<<' '<<dp[i][1]<<endl;
    }
    
    if(w)cout<<uans<<endl;
    else cout<<ans<<endl;
  }
}