poj3671 LIS

/*
Time:2019.12.4 
Author: Goven
type：LIS 
ref:
*/
//暴力 
#include<iostream>
#include<cmath>
using namespace std;

int d[30005], sum[30005];

int main()
{
    int n;
    cin >> n;
    sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        sum[i] = sum[i - 1] + d[i];
    }
    int min = 10000000, tmin;
    for (int i = 0; i <= n; i++) {//第i个为1 
        tmin = abs(sum[i] - i) + abs(sum[n] - sum[i] - 2 * (n - i));
        if (tmin < min) min = tmin;
    }
    cout << min << endl;
    return 0;
}

法2：

//DP 
//ref:https://blog.csdn.net/weixin_30826095/article/details/95959822 
#include<iostream>
#include<cmath>
using namespace std;

int dp[5];

int main()
{
    int n, d;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d;
        if (d == 1) {
            dp[2] = min(dp[1], dp[2]) + 1;
        }
        else {
            dp[2] = min(dp[1], dp[2]);
            dp[1]++;
        }
    }
    cout << min(dp[1], dp[2]) << endl;

    return 0;
}