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; } }