CodeForces - 1456A Bouncing Ball

题目大意

给出一个由 0,1 组成的序列，要从第 p 个位置开始，每次跳 k 个单位，要求跳出序列，只有当所有经过的位置都为 1 才合法。你可以花费 x 将这个序列的第一个元素删除（这个删除可以理解为要在确定 p 之前，跳之前进行），也可以花费 y 将其中一个位置改为 1 ，求能合法跳出序列的最小修改花费。

题解

dp[i]表示只通过搭柱子的方式（即消耗为x的方式）从第i个柱子上跳出去需要的花费； 从后往前确定确定dp[i]，转移方程：dp[i] = dp[i+k] + 若第i个柱子为0则+x，否则+0;； 从前往后遍历，删除若干个柱子的花费与剩下的柱子供跳出去的花费之和，用于更新最小花费，花费为：(i-1)*y + dp[i+p-1]， 其中i-1为最初移动的次数。

代码

#include
using namespace std;
const int N = 2e5+10; // 开大点 保证n+p，否则RTE 
int dp[N], n, p, k, x, y, ans, t;
string str;
int main()
{
	cin>>t;
	while(t--) {
		memset(dp, 0, sizeof dp);
		ans = 0x3f3f3f3f;
		cin>>n>>p>>k;
		cin>>str;
		getchar();
		cin>>x>>y;
		str = '.' + str;
		for(int i = n;i >= 1;i --) dp[i] = dp[i+k] + (str[i] == '1'?0:x);
		for(int i = 1;i