D. Binary String Sorting

Problem - D - Codeforces

枚举/线性dp

枚举做法：

　　　枚举每个点，满足条件左边全是0右边全是1　

　　　取每个点花费中的最小值

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll cost1 = 1e12;
const ll cost2 = 1e12 + 1;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;
        int pre_zero, pre_one;
        pre_zero = pre_one = 0;
        int n = s.size();
        int tot_zero = count(s.begin(), s.end(), '0');
        int tot_one = count(s.begin(), s.end(), '1');
        s = " " + s;
        ll minn = tot_zero*cost2;
        for (int i = 1; i <= n; i++)
        {
            pre_zero += (s[i] == '0'), pre_one += (s[i] == '1');
            if (s[i] == '0' && s[i - 1] == '1') {
                ll cost = pre_one * cost2 + (tot_zero - pre_zero) * cost2 - 1;
                minn = min(cost, minn);
            }
            else {
                ll cost= pre_one * cost2 + (tot_zero - pre_zero) * cost2 ;
                minn = min(cost, minn);
            }
        }
        cout << minn << endl;

    }
    return 0;
}

dp做法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
const ll cost1 = 1e12;
const ll cost2 = 1e12 + 1;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;
        int n = s.size();
        s = " " + s;
        vector<vector<ll>>dp(n+1,vector<ll>(4));
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (s[i] == '0') {
                dp[i][1] = dp[i - 1][1];
                dp[i][2] = dp[i - 1][2] + cost1;
                dp[i][3] = dp[i - 1][3] + cost2;
            }
            else {
                dp[i][1] = dp[i - 1][1] + cost2;
                dp[i][2] = dp[i - 1][1];
                dp[i][3] = min(dp[i - 1][2], dp[i - 1][3]);
            }
        }
        ll ans = LLONG_MAX;
        for (int i = 1; i <= 3; i++)ans = min(dp[n][i], ans);
        cout << ans << endl;
    }
    return 0;
}