题目链接：https://ac.nowcoder.com/acm/contest/6885/D
博客园食用链接：https://www.cnblogs.com/lonely-wind-/p/13507947.html
题目描述 牛妹正在玩一个数列
他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：
1.单点修改：将位置x上的数翻转（0变1,1变0）；
2.前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。
他现在想要最小化翻转次数，使得数列上的所有数都变为0。
【牛客|牛客练习赛67 D-牛牛爱数列（DP）】输入描述:
第一行，输入一个数n。
第二行，输入n个数，第i个数表示 a i a_i ai?
输出描述:
输出最小翻转次数。
输入
10
1 0 1 1 0 0 0 1 0 0
输出
3
说明
样例解释：
第一次使用（1）操作， 把2改掉： 1 1 1 1 0 0 0 1 0 0
第二次使用（2）操作， 把1-4全部改掉： 0 0 0 0 0 0 0 1 0 0
第三次使用（1）操作， 把8改掉： 0 0 0 0 0 0 0 0 0 0
备注:
数据保证 1 ≤ n ≤ 1 0 5 , 0 ≤ a i ≤ 1 1\le n\le 10^5,0\le a_i\le 1 1≤n≤105,0≤ai?≤1
emmm，我们可以考虑从前往后DP，其DP状态可以考虑设为 d p [ n ] [ 0 / 1 ] dp[n][0/1] dp[n][0/1]，其中，dp[i][0]表示将前缀 i i i全部化为0的最小步数，dp[i][1]则表示将前缀化为1的最小步数。
那么我们很容易得出其转移方程了。只不过需要注意的是最后取答案的时候由于是将整个序列变为0，所以dp[n][1]要加上1再和dp[n][0]进行比较。
以下是AC代码：
#include
using namespace std;
const int mac=1e5+10;
int dp[mac][2];
//0:change the prefix to 0,1:change the prefix to 1;
int a[mac];
int main(int argc, char const *argv[])
{
int n;
scanf ("%d",&n);
for (int i=1;
i<=n;
i++)
scanf ("%d",&a[i]);
memset(dp,0x3f3f,sizeof dp);
dp[1][0]=(a[1]==1);
dp[1][1]=(a[1]==0);
for (int i=2;
i<=n;
i++){
if (a[i]==0){
dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1);
}
else {
dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1);
dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]);
}
}
printf("%d\n",min(dp[n][0],dp[n][1]+1));
return 0;
}
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控