Codeforces Round #507 A. Palindrome Dance

厚颜无耻地在赛后发一波水题题解骗博客访问量

果然本人英语还是太菜了，出思路不到半分钟，看题却看了五分钟......QAQ

题意：给出一段由0,1,2构成的串，要求用最少的花费将其改为回文串。

可以将某个位置的2改为0或1，费用分别为a或b.

如果不能改为回文串，输出-1；

如果可以，输出最小花费。

题解：既然要改成回文串，那么就从两边开始向中间扫（从中间开始向两边扫也可以）。对于应该相同的两个位置，分以下几种情况：

·如果其中一个已经确定（0或1），另一个待填（2），那么就填上与确定的相同的数字，花费为相应的费用（a或b）

·如果两个都没有确定（均为2），那么就填成花费较小的数字。

·如果两个都确定了，且两个相同，跳过；

·如果两个都确定了，且两个不同，结束程序，输出-1；

没了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,w,b;
int a[100050];
int ans=0;
int main(){
	scanf("%d%d%d",&n,&w,&b);
	for(int i(1);i<=n;i++)scanf("%d",&a[i]);
	int l=0,r=n+1;
	for(int i(1);i<=n;i++){
		l++;r--;
		if(r<=l){
			if(r==l and a[l]==2)ans+=min(b,w);
			break;
		}
		if(a[l]==0 and a[r]==0)continue;
		if(a[l]==1 and a[r]==1)continue;
		
		if((a[l]==2 and a[r]==0) or (a[l]==0 and a[r]==2)){
			ans+=w;
			continue;
		}
		if((a[l]==2 and a[r]==1) or (a[l]==1 and a[r]==2)){
			ans+=b;
			continue;
		}
		if(a[l]==2 and a[r]==2){
			ans+=2*min(b,w);
			continue;
		}
		if(a[l]!=2 and a[r]!=2 and a[l]!=a[r]){
			printf("%d",-1);
			return 0;
		}
	}
	printf("%d",ans);
	return 0;
}