牛妹爱数列_牛客练习赛67 dp

【牛妹爱数列_牛客练习赛67】题目链接：https://ac.nowcoder.com/acm/contest/6885/D
题意

给你一个长度为n的仅包含01的序列a，并执行以下操作
单点修改：0->1 ，1->0
前缀修改：将1~x上的所有点修改
问最少操作，使得序列全变0

思路

简单dp。
dp[i][0]表示把1到i的所有点变成0需要的最少操作
dp[i][1]表示把1到i的所有点变成1需要的最少操作
转移方程：
文章图片
文章图片
当a[i]==0时，dp[i][0]要么前面全是0（dp[i-1][0]），要么前面都是1，然后前缀修改变成0（dp[i-1][1]+1）；dp[i][1]要么前面全是0，前缀修改变成1（dp[i-1][0]+1）,要么前面全是1(dp[i-1][1])，最后需要将第i位的0变成1，所以加一
当a[i]==1时，dp[i][0]要么前面全是0（dp[i-1][0]），要么前面都是1，然后前缀修改变成0（dp[i-1][1]+1）；最后需要将第i位的1变成0，所以加一；dp[i][1]要么前面全是0，前缀修改变成1（dp[i-1][0]+1）,要么前面全是1(dp[i-1][1])

AC代码

#include #define ll long long using namespace std; const int maxn = 1e5+5; int dp[maxn][3]; int a[maxn]; int main(){ int n; scanf("%d",&n); for(int i=1; i<=n; i++)scanf("%d",&a[i]); dp[0][0]=dp[0][1]=0; for(int i=1; i<=n; i++){ dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1)+(a[i]==1); dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1])+(a[i]==0); } cout << min(dp[n][0] , dp[n][1] + 1) << endl; return 0; }