首页 > 代码库 > 3D--最小代价回文串
3D--最小代价回文串
给你一个序列由),(,?组成,第i个?变成左括号,和右括号的代价不同,现在让你组成一个回文序列并让其花费的代价最少
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <stack>#include <map>#include <queue>using namespace std;struct cost { int p; int v; bool operator < (const cost& a) const { return v < a.v; }};cost make(int p, int v) { cost ret; ret.p = p; ret.v = v; return ret;}char str[50004];int main() { scanf("%s", str); int cnt = 0; int len = strlen(str); int a, b; priority_queue<cost> q; long long ans = 0; for (int i = 0; i < len; i++) { cnt += str[i] == ‘(‘; cnt -= str[i] == ‘)‘ || str[i] == ‘?‘; if (str[i] == ‘?‘) { scanf("%d %d", &a, &b); q.push(make(i, b-a)); ans += b; str[i] = ‘)‘; } if (cnt < 0 && q.empty()) { ans = -1; break; } if (cnt < 0) { cost top = q.top(); q.pop(); ans = ans - top.v; str[top.p] = ‘(‘; cnt += 2; } } if (cnt > 0) ans = -1; printf("%I64d\n", ans); if (ans != -1) printf("%s\n", str); return 0;}
3D--最小代价回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。