洛谷 CF1040A 题解

洛谷题目传送门 | CF 原题传送门

基础回文数判断题。

感觉题目翻译并不是很好，需要注意回文串中不能出现 $2$，例如 $1 0 2 0 1$ 不能作为最终答案。

思路

直接把数组从 $1$ 到 $\lfloor \frac{n}{2}\rfloor $ 扫一遍即可。

有以下几种情况需要分类讨论：

1. 如果原串首尾不同但不是 $2$，即形如 $10100$ 这样的，无法变为回文串，直接输出 $-1$；
2. 如果原串首尾都为 $2$，只需要把两个 $2$ 都换成 $0$ 和 $1$ 中代价最小的数；
3. 如果原串首尾有且仅有一个是 $2$，把那一个 $2$ 改为和另一端相同的数；
4. 最后再特判 $n$ 为奇数的情况，如果中间数为 $2$， $ans$ 需要再加上 $\min(a,b)$ 以形成不含 $2$ 的回文串。

然后这道题就很简单了。

代码

#include<cmath>
#include<iostream>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int n,a,b,t[30],ans=0;
int main()
{
	n=read();a=read();b=read();
	for(int i=1;i<=n;i++) t[i]=read();
	for(int i=1;i<=n/2;i++)
	{
		if((t[i]==0 && t[n-i+1]==1) || (t[i]==1 && t[n-i+1]==0))//首尾不同且不是2
		{
			cout<<-1<<endl;
			return 0;
		}
		else if(t[i]==2 && t[n-i+1]==2)//首尾都为2
		{
			ans+=min(a,b)*2;
			if(a<b) t[i]=t[n-i+1]=0;
			else t[i]=t[n-i+1]=1;
		}
		else if(t[i]!=2 && t[n-i+1]==2)//结尾为2
		{
			if(t[i]==0) ans+=a,t[n-i+1]=0;
			else ans+=b,t[n-i+1]=1;
		}
		else if(t[i]==2 && t[n-i+1]!=2)//开头为2
		{
			if(t[n-i+1]==0) ans+=a,t[i]=0;
			else ans+=b,t[i]=1;
		}
	}
	if(n%2==1 && t[n/2+1]==2) ans+=min(a,b);//n为奇数需要特判
	cout<<ans<<endl;
	return 0;
}