洛谷题目传送门 | CF 原题传送门
基础回文数判断题。
感觉题目翻译并不是很好，需要注意回文串中不能出现 22，例如 102011 0 2 0 1 不能作为最终答案。
思路
直接把数组从 11 到 $\lfloor \frac{n}{2}\rfloor $ 扫一遍即可。
有以下几种情况需要分类讨论：
- 如果原串首尾不同但不是 22，即形如 1010010100 这样的，无法变为回文串，直接输出 −1-1；
- 如果原串首尾都为 22，只需要把两个 22 都换成 00 和 11 中代价最小的数；
- 如果原串首尾有且仅有一个是 22，把那一个 22 改为和另一端相同的数；
- 最后再特判 nn 为奇数的情况，如果中间数为 22，ansans 需要再加上 min(a,b)\min(a,b) 以形成不含 22 的回文串。
然后这道题就很简单了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #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;
}
|
