牛客练习赛67_DP递推

2020-08-15

牛妹爱数列

十分裸的一道 DP 题感觉有点像是线性 Dp

题意:

他手里有一个长度为 n 的序列 a,保证它是一个 01 序列,并执行以下两种操作:

1.单点修改:将位置 x 上的数翻转(0 变 1,1 变 0);

2.前缀修改:将位置 1~x 上的数翻转(每个数都 0 变 1,1 变 0)。

他现在想要最小化翻转次数,使得数列上的所有数都变为 0。

很开心这次比赛中能够 A 出这道题目,其实刚开始还以为可能是思维题,因为像这种反转 01 的往往是通过先到达一种什么状态比如全是 0 或者全是 1 的然后再反转到我们想要的,但是呢本题要求最小化数目,分析了一段时间也没发现有什么好的贪心方法,只要是贪心的去搞一定会漏掉最优解的,DP 就能很好的解决这个问题,因为其可以不重不漏的将每个位置的所有状态记录下来,并且是当前位的最优的,然后向后不断地转移即可。

思路:
定义 Dp[i][j]表示前 i 个数全取 j 的最小花费为多少

考虑两件事:当前位为 0 和当前位为 1 的情况直接进行转移就好了:

若当前位为 0:
全为 1:min(前一个全为 1+1,前一个全为 0+1)
全为 0:min(前一个全为 0,前一个全为 1+1)

若当前位为 1:
全为 1:min(前一个全为 1,前一个全为 0+1)
全为 0:min(前一个全为 0+1,前一个全为 1+1)

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n;
int dp[N][3];//0代表全为0 1代表全为1 
int a[N];

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	//转移
	for(int i=1;i<=n;i++) {
		
		//当前值为0
		
		if(!a[i]) {
			
			//全为0转移
			dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
			
			//全为1转移
			dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+1); 
			
		} 
		
		else {
				
			//全为0
			dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1);
			
			//全为1
			dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1); 
					
		}
	} 
	
	cout<<dp[n][0]<<'\n';
	return 0;
		
} 


标题:牛客练习赛67_DP递推
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/08/15/1597453198914.html