题目链接
文章图片
文章图片
文章图片
【牛妹爱数列】比赛的时候想到了区间dp，但本人太鶸了居然写不出来，然后跑去看题解，发现没有区间dp，我还以为我的想法错了，然后看了本校大佬的代码发现是用区间dp做的，本蒟蒻果然是一看就懂，一做就懵，不说了，开始将解题思路吧。
明白是区间dp后还蛮简单的，转移方程非常容易想(看完别人的代码才做出来还这么硬气)，我们用dp[i][0]表示当第一个到第i个元素都是0时翻转的次数，dp[i][1]表示从第一个到第i个元素都是1时翻转的次数。第i(i>=2)个位置翻转的次数受第1个到第i-1个元素是0还是1的影响，所以很容易想到dp[i][0/1]可以由dp[i-1][0/1]转移而来。
讨论dp[i][0]，①由dp[i-1][0]得到dp[i][0]，如果第i个元素为0，则不需要再翻转，如果第i个元素为1，则翻转第i个元素即可，增加一次翻转次数。②由dp[i-1][1]得到dp[i][0],如果第i个元素为0，有两种翻转方式，一是先1-(i-1)翻转，再1-i翻转，需要翻转两次，二是第i个翻转为0，然后再翻转1-i的元素，也需要两次，所以此情况下增加两次翻转次数，如果第i个元素为1，则将1-i的元素翻转一次即可，此情况下增加一次翻转次数。
dp[i][1]也以相同方式推导即可，就不细讲了。
#include
#include
#includeusing namespace std;
const int N = 1e5 + 10;
int arr[N];
int dp[N][2];
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1;
i <= n;
i++) {
cin >> arr[i];
dp[i][0] = dp[i][1] = 0x3f3f3f3f;
}
for (int k = 1;
k <= n;
k++) {
if (arr[k]) {
dp[k][0] = min(dp[k-1][0]+1,dp[k-1][1]+1);
dp[k][1] = min(dp[k - 1][0] + 1, dp[k - 1][1]);
}
else {
dp[k][0] = min(dp[k - 1][0], dp[k - 1][1]+2);
dp[k][1] = min(dp[k - 1][0] + 1, dp[k - 1][1] + 1);
}
}
cout << min(dp[n][0], dp[n][1] + 1);
} 推荐阅读
- 补题|Educational Codeforces Round 85 (Rated for Div. 2)
- everyday|Codeforces Round #634 (Div. 3)
- 补题|Codeforces Round #635 (Div. 2)
- 补题|Codeforces Round #633 (Div. 2)
- Codeforces Round #623
- 补题|Omkar and Bed Wars
- Codeforces Round #609 (Div. 2)