QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#317715#5577. AlchemyLi__WA 0ms3640kbC++20733b2024-01-29 15:55:432024-01-29 15:55:44

Judging History

你现在查看的是最新测评结果

  • [2024-01-29 15:55:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3640kb
  • [2024-01-29 15:55:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int inf = 1100;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);	
	
	string s;
	cin>>s;

	int n=s.size();
	s=" "+s;

	vector dp(n+1,vector<i64>(2,inf));

	dp[1][0]=0;
	int m=(n+1)/2;
	for(int i=1;i<=m;i++){
		if(s[i]==s[n-i+1]) dp[i+1][0]=min(dp[i+1][0],dp[i][0]);
		else{
			dp[i+1][1]=min(dp[i+1][1],dp[i][0]+1);
			if(i!=m) dp[i+2][0]=min(dp[i+2][0],dp[i][0]+2);
		}
		if(s[i]!=s[n-i+1]) dp[i+1][0]=min(dp[i+1][0],dp[i][1]);
		else{
			dp[i+1][1]=min(dp[i+1][1],dp[i][0]+1);
			if(i!=m) dp[i+2][0]=min(dp[i+2][0],dp[i][0]+2);
		}
	}

	i64 ans=min(dp[m+1][0],dp[m+1][1]);
	cout<<ans<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

ioi

output:

0

result:

ok single line: '0'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3640kb

input:

noi

output:

2

result:

wrong answer 1st lines differ - expected: '1', found: '2'