当前位置: 首页 > news >正文

[贪心][区间dp]Zero-One Codeforces1733D1D2

This is the hard version of this problem. In this version, n≤5000n≤5000 holds, and this version has no restriction between xx and yy. You can make hacks only if both versions of the problem are solved.

You are given two binary strings aa and bb, both of length nn. You can do the following operation any number of times (possibly zero).

  • Select two indices ll and rr (l<rl<r).
  • Change alal to (1−al)(1−al), and arar to (1−ar)(1−ar).
  • If l+1=rl+1=r, the cost of the operation is xx. Otherwise, the cost is yy.

You have to find the minimum cost needed to make aa equal to bb or say there is no way to do so.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

Each test case consists of three lines. The first line of each test case contains three integers nn, xx, and yy (5≤n≤50005≤n≤5000, 1≤x,y≤1091≤x,y≤109) — the length of the strings, and the costs per operation.

The second line of each test case contains the string aa of length nn. The string only consists of digits 00 and 11.

The third line of each test case contains the string bb of length nn. The string only consists of digits 00 and 11.

It is guaranteed that the sum of nn over all test cases doesn't exceed 50005000.

Output

For each test case, if there is no way to make aa equal to bb, print −1−1. Otherwise, print the minimum cost needed to make aa equal to bb.

Example

input

6

5 8 9

01001

00101

6 2 11

000001

100000

5 7 2

01000

11011

7 8 3

0111001

0100001

6 3 4

010001

101000

5 10 1

01100

01100

output

8

10

-1

6

7

0

Note

In the first test case, selecting indices 22 and 33 costs 88, which is the minimum.

In the second test case, we can perform the following operations.

  • Select indices 11 and 22. It costs 22, and aa is 110001 now.
  • Select indices 22 and 33. It costs 22, and aa is 101001 now.
  • Select indices 33 and 44. It costs 22, and aa is 100101 now.
  • Select indices 44 and 55. It costs 22, and aa is 100011 now.
  • Select indices 55 and 66. It costs 22, and aa is 100000 now.

The total cost is 1010.

In the third test case, we cannot make aa equal to bb using any number of operations.

In the fourth test case, we can perform the following operations.

  • Select indices 33 and 66. It costs 33, and aa is 0101011 now.
  • Select indices 44 and 66. It costs 33, and aa is 0100001 now.

The total cost is 66.

In the fifth test case, we can perform the following operations.

  • Select indices 11 and 66. It costs 44, and aa is 110000 now.
  • Select indices 22 and 33. It costs 33, and aa is 101000 now.

The total cost is 77.

In the sixth test case, we don't have to perform any operation.

题意: 给出两个长度为n的01串a和b,对于a串可以选择两个位置,对于每个位置都进行一次取反,若两位置相邻则代价为x,若两位置不相邻则代价为y,问从串a经过若干次操作到达串b的最小代价。

分析: D1额外有一个条件,那就是y <= x,有了这个条件以后就会简单许多,由于不相邻位置取反的代价更小,所以尽量选取不相邻的位置进行操作,首先统计出两串所有不同的位置,我们的目标就是让所有不同的位置都被取反一次,可以将这些位置称为目标位置。如果目标位置个数为奇数那显然无解,否则一定有解。对于相邻的目标位置可以聚成一块,对于每块目标位置总能通过若干次不相邻的y操作变成1个点或者直接消除,所以可以证明只要目标位置块不是只一块且块内只有两个相邻点,那么一定可以通过(目标位置个数)/2次y操作处理完,而对于上面说的特殊情况只需要判断一下是用一次x操作还是两次y操作即可,这样就可以通过D1了。

D2要稍微复杂一些,因为它没有y <= x的条件了,由于y <= x的情况上面已经处理过了,接下来只讨论y > x的情况。在y > x的情况下,很可能多次相邻的x操作要比一次y操作更优,这样就使得没法用类似D1的贪心思路解决这个问题。根据数据范围可以猜测这道题目应该使用区间dp解决的,于是敲了O(n^3)的区间dp模板,之后考虑四边形不等式优化复杂度,但是发现区间的dp值并不具有单调性,也就是大区间的dp值不一定比其内部的小区间dp值更大,所以没办法用四边形不等式来优化。之后参考了别人的题解,发现区间dp最内层的循环是可以被贪心优化掉的,也就是区间[l, r]的断点只会是l+1或r-2,从而[l, r]只会被分割为[l, l+1] [l+2, r]或者是[l, r-2] [r-1][r]这两种情况,这样就不需要O(n)的遍历区间断点了。原因其实也比较简单,考虑一种简化情况,目前有4个位置需要更改,分别是1、3、5、7,是否有可能取3和5进行取反?显然这样不如取1、3或5、7进行取反更优。

具体代码如下:

D1

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector> 
#define int long long
using namespace std;

char a[5005], b[5005];

signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, x, y;
		scanf("%lld%lld%lld", &n, &x, &y);
		scanf("%s%s", a+1, b+1);
		vector<int> p;
		for(int i = 1; i <= n; i++)
			if(a[i] != b[i]) p.push_back(i);
		if(p.size()&1){
			puts("-1");
			continue;
		}
		if(p.size() == 2 && p[0]+1 == p[1])
			printf("%lld\n", min(x, (long long)p.size()*y));
		else
			printf("%lld\n", p.size()/2*y);
	}
	return 0;
}


D2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector> 
#define int long long
using namespace std;

const int inf = 0x3f3f3f3f3f3f3f3f;
char a[5005], b[5005];
bool dif[5005];
bool con[5005][5005];
int dp[5005][5005];

signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, x, y;
		scanf("%lld%lld%lld", &n, &x, &y);
		for(int i = 1; i <= n; i++) dif[i] = false;
		scanf("%s%s", a+1, b+1);
		vector<int> p;
		for(int i = 1; i <= n; i++)
			if(a[i] != b[i]){
				p.push_back(i);
				dif[i] = true;
			}
		if(p.size()&1){
			puts("-1");
			continue;
		}
		if(x >= y){
			if(p.size() == 2 && p[0]+1 == p[1])
				printf("%lld\n", min(x, (long long)p.size()*y));
			else
				printf("%lld\n", p.size()/2*y);
		}
		else{
			reverse(p.begin(), p.end());
			p.push_back(0);
			reverse(p.begin(), p.end());
			int cnt = p.size()-1;
			for(int i = 1; i <= cnt; i++) 
				for(int j = 1; j <= cnt; j++)
					dp[i][j] = inf;
			for(int i = 1; i < cnt; i++)
				dp[i][i+1] = min(y, x*(p[i+1]-p[i]));
			for(int len = 4; len <= cnt; len+=2)
				for(int l = 1; l+len-1 <= cnt; l++){
					int r = l+len-1;
					dp[l][r] = dp[l+1][r-1]+min(y, (p[r]-p[l])*x);
					dp[l][r] = min(dp[l][r], dp[l+2][r]+min(y, x*(p[l+1]-p[l])));
					dp[l][r] = min(dp[l][r], dp[l][r-2]+min(y, x*(p[r]-p[r-1])));
				}
			printf("%lld\n", dp[1][cnt]);
		}
	}
	return 0;
}


相关文章:

  • 06.5. 汇聚层
  • 计算机与操作系统
  • 环保电缆的几大优点
  • Linux设置开机自启动Java程序--三种方式
  • MySQL语句2.0
  • 【JSS-22双延时时间继电器】
  • jQuery插件耶
  • 老生常谈的风控模型泛化,试试从这两种维度来解决
  • 阿里云短信服务接入流程
  • 虚拟产品一天竟然能够卖七八千?是如何做到的,赶快看看
  • CV的扩散模型
  • PHP自动执行下一页脚本
  • 【数据结构与算法】单链表的查找和建立
  • TI C2000系列TMS320F2837xD开发板(DSP+FPGA)硬件规格参数说明书
  • 低代码对接腾讯云-阿里云短信平台
  • 极简ubuntu 部署k8s集群保姆教程(保证一次成功)
  • C++的内联函数、auto关键字、基于范围的for循环、空指针nullptr
  • Android修行手册 - ScrollView属性全解析
  • node fs createReadStream读取大文件,配置参数highWaterMark
  • IMX6ULL使用NXP官方mfgtool2下载方法及错误解决
  • 2022全国车辆工程专业大学排名一览表
  • 2022周口职业技术学院单招学费多少钱一年-各专业收费标准
  • 2022年中原工学院艺术类招生简章
  • 2022浙江经贸职业技术学院学费多少钱一年-各专业收费标准
  • 2022年湖南大学强基计划报名条件-报名时间-报名入口
  • 2020河北工程大学运动训练专业招生简章
  • 2022湖州有哪些民办大学?湖州所有民办大学名单一览表(1所)
  • 2022天津城市建设管理职业技术学院学费多少钱一年-各专业收费标准
  • 2022滁州学院艺术类学费多少钱一年-各专业收费标准
  • 2022云南警官学院学费多少钱一年-各专业收费标准