P13202 Teaching Assistant - Solution

Problem Statement

给定

T

个由 C 和 J 构成的字符串，按照题意的方式求出一种使得题集得分最多的方式。

Analysis

看到要求最大值，考虑贪心。

由不同情况，简单分析可得：

若 $s[i]=s[i+1]$ ，我只要令申请的题集编号也等于 $s[i]$ 就可以得到 $10$ 分
若找不到 $s[i]=s[i+1]$ ，那么令题集编号为 C 和 J 中的任意一个都可以得到最优分数 $5$ 分

Approach

使用栈存储此前未配对成功的字符，若当前找到相等字符，弹出，

ans\gets ans+10

。否则继续压入栈中，等待下一轮匹配。

相等字符匹配完后一定会剩下，设为

rest

个字符，且它们相邻一定是不同的。则这一部分产生的贡献为

\frac{rest}2 \times 5

。

因此，总答案就是

ans+\frac{rest}2 \times 5

，完成一次询问。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t,cases=1;
	cin>>t;
	while(t--){
		string s;
		int n,ans=0;
		stack<char> st;
		cin>>s;
		n=s.size();
		for(int i=0;i<n;i++){
			if(!st.empty() && s[i]==st.top()){
				st.pop();
				ans+=10;
			}else{
				st.push(s[i]);
			}
		}
		cout<<"Case #"<<cases<<": "<<ans+st.size()/2*5<<endl;
		cases++;
	} 
	return 0;
}

题解：P13202 [GCJ 2016 #3] Teaching Assistant

文章操作

P13202 Teaching Assistant - Solution

Problem Statement

Analysis

Approach

Code

相关推荐

评论

题解：P13202 [GCJ 2016 #3] Teaching Assistant