PKU 1836 Alignment

PKU

http://poj.org/problem?id=1836
n人の兵隊が順番に並んでいる。
いまi番目の兵隊の身長が与えられるので、この列から何人かの兵隊を取り除いて、全ての兵が列の前か後ろの端まで見えているようにしたい。
ある兵が列の端まで見える時、端とその兵の間にはその兵と同じ身長以上の兵がいない状態を指す。
取り除かなければならない最小の人数を求めろというような問題。

最初、単純な最長増加部分列を求める問題かと思いましたが違いました。
3
1 1 1
みたいな入力のときに2と出力してしまう解法にしていたせいで結構WAをもらいました。
最終的にはO(2^n)で書いたプログラムとの出力を比べておかしなところを探していました。

動的計画法。
i番目の人を含める時、
dp1にはi番目の人の前から最小で何人取り除かなければならないか、
dp2にはi番目の人の後ろから最小で何人取り除かなければならないかが入っています。

string in[1000];
int dp1[1000];
int dp2[1000];

bool aoverb(string&a,string&b){
  if(a[0]=='.')a="0"+a;
  if(b[0]=='.')b="0"+b;
  while(a[SZ(a)-1]=='0')a=a.substr(0,SZ(a)-1);
  while(b[SZ(b)-1]=='0')b=b.substr(0,SZ(b)-1);
  return a>b;
}

main(){
  int n;
  cin>>n;
  int ans=n;
  rep(i,n)
    cin>>in[i];

  rep(i,n)dp1[i]=dp2[n-i-1]=i;

  rep(i,n){
    rep(j,i){
      if(aoverb(in[i],in[j]))dp1[i]=min(dp1[i],dp1[j]+i-j-1);
      if(aoverb(in[n-i-1],in[n-j-1]))dp2[n-i-1]=min(dp2[n-i-1],dp2[n-j-1]+i-j-1);
    }
  }

  rep(i,n){
    rep(j,i)ans=min(ans,dp1[j]+dp2[i]+i-j-1);
  }
  cout<<ans<<endl;
}