[BOJ]18353号:兵士配置

5632 ワード
cpp algorithm baekjoon テキストリンク
質問リンク:白駿18353号です。
[質問へのアクセス]
これはどこで何度も見た問題です.最長の増加部分数列から増加ではなく減少に変更すればよい.
最長減少部分数列の大きさを求め,nから減算すると,列外を必要とする兵士の数を求めることができる.
[ソースコード]
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
int arr[2001];
int dp[2001];

int main(){
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        cin >> arr[i];
    }
    for(int i=0; i<n ; i++) {
        int now=0;
        for(int j=0 ; j<i ; j++) {
            if(arr[i]<arr[j]) now = max(now, dp[j]);
        }
        dp[i] = now+1;
    }
    int ans=0;
    for(int i=0 ; i<n ; i++) {
        ans = max(ans, dp[i]);
    }
    cout << n-ans;

    return 0;
}
linuxのデータベースおよびテーブルの変更
[Android]1行のコードでGifダイナミックマップを作成する