首页 > 代码库 > ZOJ 3829 Known Notation --贪心+找规律
ZOJ 3829 Known Notation --贪心+找规律
题意：给出一个字符串，有两种操作： 1.插入一个数字 2.交换两个字符 问最少多少步可以把该字符串变为一个后缀表达式（操作符只有*）。
解法：仔细观察，发现如果数字够的话根本不用插入，数字够的最低标准为‘*‘的个数+1，因为最优是 ‘12*3*..‘ 这种形式，所以先判断够不够，不够就补，然后从左往右扫一遍，如果某个时刻Star+1>Num，那么从开始到这一段是不合法的，要把那个‘*‘与后面的一个数字交换，此时Star--,Num++。然后步数++。这样得出的结果就是最后的最小步数。
脑子太笨了，当时没有想到仔细找找规律，还以为是什么高贵的dp呢。。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;char ss[2005];int main(){ int t,Num,Star,i; scanf("%d",&t); while(t--) { scanf("%s",ss); Num = Star = 0; int len = strlen(ss); for(i=0;i<len;i++) { if(ss[i] == ‘*‘) Star++; else Num++; } int lack = Star+1-Num; lack = max(lack,0); int ans = lack; int star = 0, num = lack; for(i=0;i<len;i++) { if(ss[i] == ‘*‘) star++; else num++; if(star+1 > num) star--,num++,ans++; } cout<<ans<<endl; } return 0;}
ZOJ 3829 Known Notation --贪心+找规律
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。