C++(clang++ 11.0.1) 解法, 执行用时: 5ms, 内存消耗: 2444K, 提交时间: 2022-12-09 18:38:49

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int dp[N][N][2];
int pos[N];

signed main(){
	int n;
	cin>>n;
	int num;
	string ss;
	cin>>ss;
	ss = " "+ss;
	num = 0;
	for(int i = 1;i<=n;i++){
		if(ss[i]=='1'){
			num++;
			pos[num] = i;
		}
	}
	if(n-num<n/2){
		cout<<"-1"<<endl;
		return 0;
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0][0] = 0;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=i&& j<=num;j++){
			if(j>=1) dp[i][j][1] = dp[i-1][j-1][0]+abs(pos[j] - i);
			dp[i][j][0] = min(dp[i-1][j][0],dp[i-1][j][1]);
		}
	}
	cout<<min(dp[n][num][0],dp[n][num][1])<<endl;
	
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 79ms, 内存消耗: 1688K, 提交时间: 2022-12-03 16:03:23

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