Codeforces Round #647 (Div. 2) – Johnny and Contribution

今天真是不适合写题的一天,不适合打周赛也不适合补cf,我哭哭。不过确实也学到了许多,比如说我终于知道了cf是可以看测试数据的,我微笑。浪费了好久……第一个AC是我快晕倒了去网上找了份代码交了一下。

E. K-periodic Garland

题意

给出一串01串和一个数字 $k$,一次翻转记为一次操作。使用最少的操作,使串中相邻的 $1$ 之间间隔为 $k$。字符串不是环。

思路

这个思路是我在b站和一个大二acmer学到的,我好菜啊qwq。

【状态表示】

dp[i] 表示以 i 结尾,并且 i1 的最少翻转次数。

【状态转移】

分两种情况:

  • i 是第一个 1 所在位置,所以 [0, i-1] 范围内必须全为 0 。可以先求一个关于 1 的前缀和方便处理。在这种情况下, dp[i] = sum[i-1] + (s[i] == '0')
  • i 不是第一个 1 所在位置,所以可以从 dp[i-k] 转移过来。转移过来的条件是 [i-k+1, i-1] 范围内必须全为 0 。 这种情况下, dp[i] = (s[i] == '0') + (one[i-1]-one[i-k]) + dp[i-k]

【答案记录】

根据 dp[i] 的定义,区间 [i+1, n] 应该全部为 0 ,所以 ans = min(ans, dp[i]+one[n]-one[i])

【特殊情况】

如果字符串本身就是纯0串,直接返回 0

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
const int INF = 1e9 + 5;

char s[MAXN];
int dp[MAXN], one[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        int n, k; scanf("%d %d %s", &n, &k, s+1);
        one[0] = 0; for(int i=1; i<=n; i++) one[i] = one[i-1] + (s[i] == '1');
            
        if(one[n] == 0) {
            printf("0\n");
            continue;
        }
        
        int ans = INF; dp[0] = 0;
        for(int i=1; i<=n; i++) {
            dp[i] =  (s[i] == '0') + one[i-1];
            if(i >= k) dp[i] = min(dp[i], (s[i] == '0') + (one[i-1]-one[i-k]) + dp[i-k]);
        }

        for(int i=1; i<=n; i++) ans = min(ans, dp[i]+one[n]-one[i]);
        printf("%d\n", ans); 
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇