C. Bouncing Ball(从后往前的前缀和)

Problem - 1415C - Codeforces

 

你正在为某个手机游戏创建一个游戏关卡。这个关卡应该包含一些从左到右排列的单元格，并以从1开始的连续整数编号，在每个单元格中，你可以放一个平台，也可以让它空着。

为了通过一个关卡，玩家必须从左边扔出一个球，使其首先落在p单元的平台上，然后弹开，再弹开(p+k)单元的平台，然后是(p+2k)单元的平台，以此类推，每隔k个平台，直到它走得比最后一个单元远。如果这些单元中的任何一个没有平台，你就不能用这些p和k通过关卡。

你已经有了一些关卡模式a1, a2, a3, ..., an，其中ai=0表示i单元中没有平台，ai=1表示有一个。你想修改它，以便在给定的p和k下通过关卡。在y秒内，你可以完全删除第一个单元格，减少一个单元格的数量，并重新计算其他单元格，保持它们的顺序。你不能做任何其他操作。你不能将单元格的数量减少到小于p。

第三例测试案例的插图。打叉的是被删除的单元格。蓝色平台是新添加的。
在给定的p和k下，你需要多少秒才能使这一关通过？

输入
第一行包含测试用例的数量t（1≤t≤100）。测试用例的描述如下。

每个测试用例的第一行包含三个整数n、p和k（1≤p≤n≤105，1≤k≤n）--你有多少个单元格，应该包含一个平台的第一个单元格，以及需要的球弹跳周期。

每个测试案例的第二行包含一个字符串a1a2a3...an（ai=0或ai=1）--不含空格的初始模式。

每个测试案例的最后一行包含两个整数x和y（1≤x,y≤104）--增加一个平台和删除第一个单元格相应所需的时间。

测试用例的n之和不超过105。

输出
对于每个测试用例输出一个整数--你需要相应修改水平的最小秒数。

可以证明，总是有可能使关卡通过的。

例子
input
3
10 3 2
0101010101
2 2
5 4 1
00000
2 10
11 2 3
10110011000
4 3
输出
2
4
10

题解:
问题就是删除前几个格子,加上个板子所需时间最小,并且能跳到>=n

正着想枚举删掉的个数再求时间,肯定会t

不如反过来想n->1

首先a[i] == 0 dp[i] = x

if(i+k<=n) dp[i] += dp[i+k]

这样我们就知道从i开始到达到条件需要铺板子的时间了

剩下就是枚举删除几个板子使时间最小了

因为起点从p开始,所以从p开始枚举

ans = min(ans,dp[i]+(i-p)*y)

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
char a[200050];
int dp[200050];
void solve()
{
	int n,p,k;
	cin >> n>>p>>k;
	for(int i = 1;i <= n;i++)
	cin >> a[i],dp[i] = 0;
	int x,y;
	cin >>x >>y;
	for(int i = n;i >= 1;i--)
	{
		if(a[i] == '0')
		dp[i] = x;
		if(k+i <= n)
		{
			dp[i] +=dp[i+k];
		}
	}
	int ans = 1e9;
	for(int i = p;i <= n;i++)
	{
		ans = min(ans,dp[i]+(i-p)*y);
	}
	cout<<ans<<"\n";
}
int main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
//
//