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]);
にしていた。
Get up! 明日のSUPER ST@R!