Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2) C. Bouncing Ball (后缀和,枚举)

题意:有一长度为\(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;

}

巴特西

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2) C. Bouncing Ball (后缀和,枚举)

最新文章

热门文章