codeforces-#642-E

codeforces-#642-E

七月 17, 2020

E. K-periodic Garland

题意

给出一个01串长为n<1e6

要求将它改为1的间隔=k的01串

比如k=3则

“00010010”,”1001001”,”00010”,”0000” 都合法

每次操作只改变一个位置的0/1状态

问最小操作次数

题解

设计dp[i][0] 表示第i位是第一个1

dp[i][1] 表示第i为不是第一个1

同时维护前缀pre[i]表示到第i位有几个1

那么可以得到转移方程

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++){
	int last;
    if(i-k>0){
    	last=min(dp[i-k][0],dp[i-k][1]);///到第i-k位合法的最小操作
        dp[i][1]=last+pre[i-1]-pre[i-k]+(arr[i-1]=='0');
        ///dp[i][1]是由dp[i-k][1]+中间全变0,第位变1的操作次数
        ///或dp[i-k][0]+中间全变0,第位变1的操作次数或者说退化成dp[i][0]含义
        ///两者中取min
    }
    ans=min(ans,min(dp[i][1],dp[i][0])+(pre[n]-pre[i]));
    ///ans是到第i位合法的最小操作次数+后缀全为0的操作次数取min
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e6+5;
int pre[Max];
int dp[Max][2];
int main() {
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n,k;cin>>n>>k;
        string arr;cin>>arr;
        bool flag=0;
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1]+(arr[i-1]=='1');
            dp[i][1]=Max;
            dp[i][0]=pre[i-1]+(arr[i-1]=='0');
            if(pre[i]>0)flag=1;
        }
        if(!flag){
            cout<<0<<endl;
            continue;
        }
        int ans=Max;
        for(int i=1;i<=n;i++){
            int last;
            if(i-k>0){
                last=min(dp[i-k][0],dp[i-k][1]);
                dp[i][1]=last+pre[i-1]-pre[i-k]+(arr[i-1]=='0');
            }
            ans=min(ans,min(dp[i][1],dp[i][0])+(pre[n]-pre[i]));
        }
        cout<<ans<<endl;
    }
}

其他dp设计方案

dp[i][0/1]表示到第i位合法时第i位是0还是1