传送门
题意:一个长为n的字符串,含有大写字母或小写字母,最多进行k次操作,将长为l范围内的字符全部变为小写或全部变为大写,求min(lower,upper)的最小值,其中lower是小写字母的数量,upper是大写字母的数量.n,k,l<=1e6,l<=n
二分+动态规划.
首先二分枚举每次操作最少使lower(upper)数量减少y,然后dp转移,只有在lower(upper)的数量大于等于y时才发生转移,dp值表示在最少减少y之外额外减少的lower(或upper)的值,最后需要使得操作次数<=k;经过二分得到最小的k值,此时减少后lower的数量即为答案.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
typedef long double lb;
#define ri register int
const lb PI=3.141592653589793238462643383279;
const ll inf=1000000000000000000ll;
const int N=1000005,M=998244353;
int n,i,k,p,j,l,r,ans;
int s[N],t[N];
long long dp[N];
char c[N];
int check(int y,bool type,bool f)
{int i;for(i=1;i<=n;++i){if(c[i]>='A'&&c[i]<='Z')s[i]=type;elses[i]=type^1;s[i]+=s[i-1];}cout<<y<<endl;for(i=1;i<=n;++i){dp[i]=max(dp[i-1],(i-p<0?0:dp[i-p]-s[i-p])+s[i]-y);if(dp[i-1]>(i-p<0?0:dp[i-p]-s[i-p])+s[i]-y)t[i]=t[i-1];elseif(dp[i-1]<(i-p<0?0:dp[i-p]-s[i-p])+s[i]-y)t[i]=t[i-p]+1;elset[i]=min(t[i-1],t[i-p]+1);// cout<<dp[i]<<" "<<t[i]<<endl;}if(f){ans=min(1ll*ans,s[n]-dp[n]-k*y);}return t[n];
}
int main()
{scanf("%d %d %d",&n,&k,&p);scanf("%s",c+1);l=0,r=p;ans=n;while(l<r){int mid=l+r>>1;if(check(mid,0,0)<=k)r=mid;elsel=mid+1;}check(l,0,1);l=0,r=p;while(l<r){int mid=l+r>>1;if(check(mid,1,0)<=k)r=mid;elsel=mid+1;}check(l,1,1);cout<<ans;
}