QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317733#5577. AlchemyLi__WA 1ms3812kbC++20780b2024-01-29 16:20:512024-01-29 16:20:52

Judging History

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

  • [2024-01-29 16:20:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3812kb
  • [2024-01-29 16:20:51]
  • 提交

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;
	if(n%2!=0){
		s.erase(m,1);
		m--;
		n--;
	}
	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][1]+1);
			if(i!=m) dp[i+2][0]=min(dp[i+2][0],dp[i][1]+2);
		}
	}
	i64 ans=min(dp[m+1][0],dp[m+1][1]);
	cout<<ans<<'\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

input:

ioi

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

noi

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

ctsc

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3488kb

input:

fool

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

vetted

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

aa

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

ic

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

tlffohemdcncrfrxaqsbzcoyodvbxmhqukvfpahnakexcmacqa

output:

12

result:

ok single line: '12'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

qrgld

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

ejyfprguvwrnrsrykyrotmdjuzroohvlxqhvyeukkvmshtpczyyecpzhsqvkxueqvhlxldhofrzcjdhtotykgrsdnrnvuyrphyjy

output:

26

result:

ok single line: '26'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

xcpccpcy

output:

2

result:

ok single line: '2'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

abpccpcp

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

ixpccpci

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

xcxccpci

output:

2

result:

ok single line: '2'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

xcpxcpci

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

ixxccpci

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

ixpxcpci

output:

2

result:

ok single line: '2'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

ixpxxycpci

output:

3

result:

ok single line: '3'

Test #19:

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

input:

yxxxyxxxxxyyxxyxxyxyyyxyxyyyyxyxxxxxxxxxxxxyyxxyxyxyyxxyyxyxxyyxxyyyyyyxxyyxxyyxxxxyyyxxxyyxyxyxxyxx

output:

21

result:

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