首页 > 代码库 > Codeforces3D--最小费用回文串
Codeforces3D--最小费用回文串
#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#include <string.h>#include <iostream>#include <vector>#include <list>#include <stack>#include <queue>#include <map>#include <set>#include <algorithm>typedef short int int16;///32767typedef int int32;///2147483647typedef long long int64;///9223372036854775807const double PI=acos(-1.0);///3.141593const long long MOD=(long long)1E9+7LL;///1000000007template <class T> T Susake_pow(T a,T b)///pow{T res;if(b==0) return 1;else while((b&1)==0){b>>=1;a*=a;}res=a;b>>=1;while(b!=0){a*=a;if((b&1)!=0)res*=a;b>>=1;}return res;}template<class T> inline T gcd(T a,T b)///gcd{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}template<class T> inline T lcm(T a,T b)///lcm{if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}template<class T> inline char *Susake_nsystem(T n)///itoa(26){T t=0,i;char *s,*p;s=(char *)malloc(sizeof(char)*1000);p=(char *)malloc(sizeof(char)*1000);while(n){s[t]=n%26+64;if(s[t]==64){s[t]+=26;n-=26;}t++;n/=26;}s[t]=‘\0‘;for(i = 0; i < t; i++)p[i]=s[t-1-i];p[i]=‘\0‘;free(s);return p;}int Susake_system(char *s)///atoi(26){int len=strlen(s),i,sum=0;char p[1000];for(i=0;i<len;i++)p[i]=s[len-1-i]-64;for(i=0;i<len;i++)sum+=p[i]*Susake_pow(26,i);return sum;}char str[55555];std::priority_queue <std::pair <int, int> > Q;int main(int argc, char *argv[]){ int a, b; scanf("%s", str); char *p = str; int lf = 0; long long sum = 0; bool noans = false; while (*p) { if (*p == ‘(‘) lf++; if (*p == ‘)‘) lf--; if (*p == ‘?‘) { scanf("%d%d", &a, &b); if (noans) { p++; continue;} *p = ‘)‘; lf--; sum += b; Q.push(std::pair <int, int>(b - a, p - str)); } while (!Q.empty() && lf < 0) { std::pair <int, int> t = Q.top(); sum -= t.first; *(str + t.second) = ‘(‘; lf += 2; Q.pop(); } if (lf < 0) noans = true; p++; } if (noans || lf) puts("-1"); else { printf("%lld\n", sum); printf("%s\n", str); } return 0;}
Codeforces3D--最小费用回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。