牛客练习赛106 G

题目
题意: 给定一个长度为 nn的 01 序列 S，求最少需要多少次操作能使得最终得到的 01 序列不存在两个相邻位置值都为 1。
若无解则输出 -1。
思路: dp。
f[i][j]: 表示第i个1放到j这个位置时的最小操作数。
f[i][j] = f[i-1][k], 1<=k<=j-2.
第二维只需要枚举到j-2，就能保证第i个1与前边的1是不冲突的。
除此之外，可以用记忆化搜索来实现，会更容易一些。
dfs(idx,cur): 当前枚举到第idx个1，位置在cur，需要的总花费是多少.
如果放到最后一个了，返回0，边界条件。如果cur大于n，idx还没有放完，说明当前方案无解，返回INF。
cur这个位置要么放1，要么不放1。
如果不放1，消耗就是dfs(idx,cur+1)，直接看下一个位置。
如果放1，消耗就是dfs(idx+1,cur+2)，当前位置放了必须隔一个位置才能继续放。比较好理解一些。
代码:

#include
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int n,m,k,T;
int a[N];
vector<int> va;
ll f[502][502];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;++i) 
	{
		scanf("%1d",&a[i]);
		if(a[i]==1) va.push_back(i);
	}
	if(va.size()>(n+1)/2)
	{
		cout<<-1; return ;
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i) f[0][i] = abs(i-va[0]);
    for(int i=1;i<va.size();++i)
    {
    	for(int j=1;j<=n;++j)
    	{
    		for(int k=1;k<=j-2;++k)
			{
				f[i][j] = min(f[i][j],f[i-1][k]+abs(va[i]-j));
			}
		}
	}
	ll ans = 1e18;
	for(int i=1;i<=n;++i) ans = min(ans,f[va.size()-1][i]);
	cout<<ans;
}
signed main(void)
{
//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	T = 1;
//	cin>>T;
	while(T--)
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

记忆化搜索:

#include
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int n,m,k,T;
int a[N];
vector<int> va;
map<int,map<int,ll> > mp;
ll dfs(int cur,int idx)
{
	if(idx==va.size()) return 0;
	if(cur>n) return 1e18;
	if(mp[cur][idx]) return mp[cur][idx];
	return mp[cur][idx] = min(dfs(cur+1,idx),dfs(cur+2,idx+1)+abs(va[idx]-cur));
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;++i) 
	{
		scanf("%1d",&a[i]);
		if(a[i]==1) va.push_back(i);
	}
	if(va.size()>(n+1)/2)
	{
		cout<<-1; return ;
	}
    cout<<dfs(1,0);
}
signed main(void)
{
//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	T = 1;
//	cin>>T;
	while(T--)
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38