题解 | #三子棋#

G.

设 $d{p}_{i,j}dp\_\{i,j\}$ 为考虑前 $ii$ 个 $11$ 交换到第 $jj$ 个时前$ii$个 $11$ 均互不相邻的最小操作数。

枚举 $jj$ 的同时从 $j-2j-2$ 开始往低位转移即可。

时间复杂度 $O(n^3)O(n^3)$。

#include<bits/stdc++.h>
using namespace std;
int dp[505][505];
string s;
int a[505];
int b[505];
int n;
int main()
{
    cin>>n;
    cin>>s;
    s = " "+s;
    int cnt = 0;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    for(int i = 1;i<=n;++i)
        if(s[i]=='1')
            a[++cnt] = i;
    if(cnt>(n+1)/2)
    {
        cout<<-1<<'\n';
        return 0;
    }
    for(int i = 1;i<=n;++i)
        dp[1][i] = abs(i-a[1]);
    for(int i = 2;i<=cnt;++i)
        for(int j = i;j<=n;++j)
            for(int k = j-2;k>=i-1;--k)
                dp[i][j] = min(dp[i-1][k]+abs(j-a[i]),dp[i][j]);
    int ans = 0x3f3f3f3f;
    for(int i = 1;i<=n;++i)
        ans = min(ans,dp[cnt][i]);
    cout<<ans<<'\n';
    return 0;
}