【牛妹爱数列_牛客练习赛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])
#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;
}
推荐阅读
- 题目|C. Ayoub and Lost Array(思维dp)
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils(dp px 互相转换)