C - Bouncing Ball

小灰灰 2021-07-16 23:28 257阅读 0赞

C - Bouncing Ball

C. Bouncing Ball  
time limit per test  
1 second  
memory limit per test  
256 megabytes  
input  
standard input  
output  
standard output

You’re creating a game level for some mobile game. The level should contain some number of cells aligned in a row from left to right and numbered with consecutive integers starting from 1

, and in each cell you can either put a platform or leave it empty.

In order to pass a level, a player must throw a ball from the left so that it first lands on a platform in the cell p  
, then bounces off it, then bounces off a platform in the cell (p+k), then a platform in the cell (p+2k), and so on every k-th platform until it goes farther than the last cell. If any of these cells has no platform, you can’t pass the level with these p and k

You already have some level pattern a1  
, a2, a3, …, an, where ai=0 means there is no platform in the cell i, and ai=1 means there is one. You want to modify it so that the level can be passed with given p and k. In x seconds you can add a platform in some empty cell. In y seconds you can remove the first cell completely, reducing the number of cells by one, and renumerating the other cells keeping their order. You can’t do any other operation. You can not reduce the number of cells to less than p

Illustration for the third example test case. Crosses mark deleted cells. Blue platform is the newly added.

What is the minimum number of seconds you need to make this level passable with given p  
and k

?  
Input

The first line contains the number of test cases t  
(1≤t≤100

). Description of test cases follows.

The first line of each test case contains three integers n  
, p, and k (1≤p≤n≤105, 1≤k≤n

) — the number of cells you have, the first cell that should contain a platform, and the period of ball bouncing required.

The second line of each test case contains a string a1a2a3…an  
(ai=0 or ai=1

) — the initial pattern written without spaces.

The last line of each test case contains two integers x  
and y (1≤x,y≤104

) — the time required to add a platform and to remove the first cell correspondingly.

The sum of n  
over test cases does not exceed 105

.  
Output

For each test case output a single integer — the minimum number of seconds you need to modify the level accordingly.

It can be shown that it is always possible to make the level passable.

思路：首先按照暴力的思路，我们可以从0个删除一直到删除n-p个数，然后每次求一个min，（对于每一次从删除后的第一个数开始每隔k个数pattern为0则加上x，再加上相应的删除的个数\*k）。但这会毫无疑问会TLE，我们观察一下可以发现这是因为我们每一次都对后面的所有需要加pattern求了一次，但其实我们可以反复利用已经求到的总和。所以只需对所有的（0，1，2，3…k-1）求一次总和，后面可反复利用，细节见代码。

Code

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e5 + 5;
    int lst[Max];
    ll sec[Max];
    
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, p, k;
    		cin >> n >> p >> k;
    		for (int i = 1;i <= n;i++)
    		{ 
    			char u;cin >> u;
    			lst[i] = u - '0';
    		}
    		int x, y;cin >> x >> y;
    		for (int i = 0;i <= k - 1;i++)
    		{ 
    			int d = p+i;
    			while (d <= n)
    			{ 
    				if (lst[d] == 0)sec[i]+=x;
    				d += k;
    			}
    		}
    		ll ans = 1e18 + 5;
    		for (int i = p;i<= n;i++)
    		{ 
    			ans = min(ans, sec[(i - p) % k] + (i - p) * y);
    			if (lst[i] == 0)sec[(i - p) % k] -= x;
    		}
    		cout << ans << endl;
    	}
    }