- 题意:有一长度为\(n\)的平台,平台有的位置有木桩,可以使小球弹起来,小球必须从第\(p\)个位置开始,而且每次都会向右弹\(k\)个单位,然后有的位置是没有木桩的,你可以在这些的空的位置放一个木桩,需要花费\(x\),在开始的时候,你可以删除前几个单位,每个单位花费\(y\),问最少花费多少使得小球能够弹出平台外.
- 题解:刚开始看错题意了,以为可以删除任意位置的单位,结果发现这个动态的过程根本没办法维护,又重新看了一眼题面发现只能删去相对第一个单位,然后这题就是一道sb题了,我们可以记录一个后缀和,表示每个位置之后小球要弹的位置上总共有多少个\(1\),然后我们去枚举起点,更新最小值就行了.
- 代码:
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;int t;
int n,p,k;
string s;
int x,y;
int cnt[N];int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n>>p>>k;
cin>>s;
cin>>x>>y;
me(cnt,0,sizeof(cnt));
per(i,n-1,0){
if(i+k<=n-1) cnt[i]=cnt[i+k];
if(s[i]=='1'){
cnt[i]++;
}
}
int ans=INF;
rep(i,p-1,n-1){
int cost=(i-p+1)*y;
int cur=n-1-i;
cur/=k;
cur++;
if(cnt[i]<cur) cost+=(cur-cnt[i])*x;
ans=min(ans,cost);
}
cout<<ans<<'\n';
} return 0;
}
