Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

算法与证明

Posted by cavatina2016 at 2020-08-01 01:14:00 on Problem 3991
贪心算法:
1.从字符串头开始扫描;设res为计算结果;
2.想象有一个堆栈,遇到“{”就放到堆栈里,遇到“}”就把堆栈POP出一个“{”来匹配;
3.如果遇到“}”的时候堆栈为空,就把这个“}”替换为“{”放到堆栈里,res加1;
4.如果字符串扫描完了,堆栈里还有X个“{”(X肯定是偶数),就把栈顶的X/2个“{”替换为“}”与剩下的X/2个“{”匹配,res加上X/2;
5.实际代码不需要堆栈,只需一个计数器


证明:
1.每次堆栈为空的时候遇到“}”,说明已扫描那部分字符串的“}”比“{”多1个,要实现完全匹配,至少要把1个“}”替换为“{”;
2.最后堆栈里剩下的X个“{”(只有最底下那个可能是“}”置换来的),要实现完全匹配,至少要把X/2个“{”替换为“}”
3.于是计算出了最小替换个数的一个下限,这个下限正好是上面算法得到的结果

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator