POJ 1836 Alignment

問題文

DP強化週間。

一列に兵が並んでおり、ここから何人か除いた時に、
残りの兵いずれもが少なくとも隊列の左右のどちらかの
端(端の兵ではない)が見通せるようにしたい。端が見通せる条件は
端までに自分より同じか背の高い兵が一人もいない時とする。
取り除けばよい兵の最小数を求めよ。

要は取り除いたあとに隊列が↓こんな感じになってればいい。

なので左右からLISを求めていって、iを0~n-2で走査して
max(l[i], r[i + 1])を求める。これが取り除いたあとの
最長の兵の数。あとは元の兵の数からこれを引けばいい。
dp[i]:=(最後がi番目の兵であるLISの長さ)でDP。
それを左右からi番目までで最長のLISの長さに変えて
l[i], r[i]に入れている。

以下ソース。

int dp1[1001];
int l[1001];
int dp2[1001];
int r[1001];
double h[1000];

void lis(int *dp, int *w, int N){
  int res = 0;
  for(int i = 0; i < N; i++){
    dp[i] = 1;
    for(int j = 0; j < i; j++){
      if(h[i] > h[j])
	dp[i] = max(dp[i], dp[j] + 1);
    }
    res = max(res, dp[i]);
    w[i] = res;
  }
}

int main(){
  int n; cin >> n;
  for(int i = 0; i < n; i++) cin >> h[i];
  memset(dp1, 0, sizeof(dp1));
  memset(dp2, 0, sizeof(dp2));
  memset(l, 0, sizeof(l));
  memset(r, 0, sizeof(r));

  //DP
  lis(dp1, l, n);
  reverse(h, h + n);
  lis(dp2, r, n);
  reverse(r, r + n);

  int ans = 0;
  for(int i = 0; i < n - 1; i++)
    ans = max(ans, l[i] + r[i + 1]);

  cout << n - ans << endl;
  return 0;
}

何回かWAをもらった。
max(ans, l[i] + r[i]);
にしていた。