手間取ったけどなんとか全完。
http://codeforces.com/contest/935/problem/E
問題
括弧と1桁の数字と演算子で構成された数式が与えられる。
ただし演算子の種別は不明で、+と-の総数だけが与えられている。
- と-を最適に配置すると、この式の最大値はいくつになるか。
なお、+-のどちらかは100個以下である。
解法
数式をDFSの要領でParseしつつ、+-の少ない方に対し、使用回数毎に数式の最大値を最小値を求め、DPしていこう。
string E; int P,M; int cur; vector<pair<int,int>> hoge() { vector<pair<int,int>> R; int S=min(P,M); int i; FOR(i,S+1) R.push_back({-1<<20,1<<20}); if(E[cur]=='(') { cur++; vector<pair<int,int>> A,B; A=hoge(); assert(E[cur]=='?'); cur++; B=hoge(); assert(E[cur]==')'); cur++; int x,y; if(P<=M) { FOR(x,P+1) FOR(y,P+1) { if(x+y<=P) { R[x+y].first=max(R[x+y].first,A[x].first-B[y].second); R[x+y].second=min(R[x+y].second,A[x].second-B[y].first); if(x+y+1<=P) { R[x+y+1].first=max(R[x+y+1].first,A[x].first+B[y].first); R[x+y+1].second=min(R[x+y+1].second,A[x].second+B[y].second); } } } } else { FOR(x,M+1) FOR(y,M+1) { if(x+y<=M) { R[x+y].first=max(R[x+y].first,A[x].first+B[y].first); R[x+y].second=min(R[x+y].second,A[x].second+B[y].second); if(x+y+1<=M) { R[x+y+1].first=max(R[x+y+1].first,A[x].first-B[y].second); R[x+y+1].second=min(R[x+y+1].second,A[x].second-B[y].first); } } } } } else { R[0]={(int)(E[cur]-'0'),(int)(E[cur]-'0')}; cur++; } return R; } void solve() { int i,j,k,l,x,y; string s; cin>>E; cin>>P>>M; auto r=hoge(); cout<<r[min(P,M)].first<<endl; }
まとめ
-
- のどちらかだけ数の上限が指定される、って珍しいな。