E. K-periodic Garland
对于一个序列 显然我们只有%m相同的位置上才能放置1
不然肯定不合法
所以我们把他分成m个部分 记录一下总和
然后转化一下题意 发现他就是一个
然后我们直接暴力 然后贴板子就可以了
greedy做法
void solve(){
int n,m;cin>>n>>m;
string s;cin>>s;
vector<int>v[m],cnt(m);
int sum=0;
for(int i=0;i<n;i++){
v[i%m].push_back(s[i]-'0');
if(s[i]-'0')sum++,cnt[i%m]++;
}
int ans=INF;
for(int i=0;i<m;i++){
int now=0;
for(auto j:v[i]){
if(j==1)now++;
else now--;
if(now<0)now=0;
ans=min(ans,sum-now);
}
}
cout<<ans<<endl;
}
然后其实我们还可以dp
我们发现他其实肯定是这样的 中间一坨是1 两端是0
当然这些个段的长度都可以是0
所以我们的dp状态就出来了
dp[i][0/1/2]表示第i个数字属于第几个段min
这样的转移也特别简单
答案就是三个取min
这里估计大家会有疑问
这样不是只会有
000011110000
0000011111
00000000
这三种情况吗
但是我们这里的dp[][1]是直接可以从dp[0][]转移的意思就是可以不要前面一坨0
所有就包含了所有情况
111111000000
11111111111111
dp做法
void solve(){
int n,m;cin>>n>>m;
string s;cin>>s;
vector<int>v[m],cnt(m);
int sum=0;
for(int i=0;i<n;i++){
v[i%m].push_back(s[i]-'0');
if(s[i]-'0')sum++,cnt[i%m]++;
}
int ans=INF;
for(int i=0;i<m;i++){
while((int)v[i].size()&&!v[i].back())v[i].pop_back();
int dp[v[i].size()+1][3];
memset(dp,0x3f3f,sizeof dp);
dp[0][0]=dp[0][1]=dp[0][2]=0;
//v[i]
for(int j=1;j<=v[i].size();j++){
dp[j][0]=dp[j-1][0]+(v[i][j-1]!=0);
dp[j][1]=min(dp[j-1][1],dp[j-1][0])+(v[i][j-1]!=1);
dp[j][2]=min(dp[j-1][1],dp[j-1][2])+(v[i][j-1]!=0);
}
ans=min(ans,sum-cnt[i]+min({dp[v[i].size()][0],dp[v[i].size()][2],
dp[v[i].size()][1]}));
}
cout<<ans<<endl;
}
标签:string,min,int,Codeforces,cin,642,Div,dp
From: https://www.cnblogs.com/ycllz/p/16880140.html