思路： 简单模拟下。从左向右扫描一次，求出挖出该区间空地的花费，并取个最小值即可。
至于怎么求区间内的高度最小值，就用线段树就好了。
#include <bits/stdc++.h> #define PB push_back #define MP make_pair using namespace std; typedef long long LL; typedef pair<int,int> PII; #define PI acos((double)-1) #define E exp(double(1)) #define K 1000000+9 struct node1 { int h,kind; }mp[K]; int n,m; char ss[K]; struct node { int mi; int left,right; }tree[4*K]; int build(int id,int l,int r) { tree[id].left=l;tree[id].right=r; if(l==r) tree[id].mi=mp[l].h; else { build(2*id,l,(l+r)/2); build(2*id+1,(l+r)/2+1,r); tree[id].mi=min(tree[2*id].mi,tree[2*id+1].mi); } return 0; } int query(int id,int l,int r) { if(l==tree[id].left && r==tree[id].right) return tree[id].mi; int mid=(tree[id].left+tree[id].right)>>1; int ret=0x3f3f3f3f; if(r<=mid) ret=min(ret,query(id*2,l,r)); else if(l>=mid+1) ret=min(ret,query(id*2+1,l,r)); else { int a,b; a=query(id<<1,l,mid); b=query((id<<1)+1,mid+1,r); return min(a,b); } return ret; } double get_ans(int x,int mi) { double ans=0; ans+=mp[x].h-mi; ans+=mp[x].kind==0?0:0.5; return ans; } int main(void) { int t,cs=1;cin>>t; while(t--) { double ans,sum=0; scanf("%d%d%s",&n,&m,&ss[1]); mp[0].h=1; for(int i=1,ls=0;i<=n;i++) { mp[i].h=mp[i-1].h+ls; if(ss[i]=='_')ls=0,mp[i].kind=0; else if(ss[i]=='/')ls=1,mp[i].kind=1; else if(ss[i]=='\')ls=0,mp[i].kind=2,mp[i].h--; //printf("%d : %d ",i,mp[i].h); } build(1,1,n); for(int i=1,mi=query(1,1,m);i<=m;i++) sum+=get_ans(i,mi); ans=sum; for(int i=m+1,ls=query(1,1,m);i<=n;i++) { int mi=query(1,i-m+1,i); sum-=get_ans(i-m,ls); sum+=get_ans(i,mi); if(ls>mi) sum+=(m-1.0)*(ls-mi); else if(ls<mi) sum-=(mi-ls)*(m-1.0); ls=mi; ans=min(sum,ans); } printf("Case #%d: %.1f ",cs++,ans); } return 0; }