題解

一道很有意思的題目，同時(shí)把動(dòng)態(tài)規(guī)劃和語(yǔ)法樹(shù)結(jié)合起來(lái)，很有新意，思路我是想出來(lái)了，但是我的寫(xiě)法較為麻煩，從別人的submission中找了一個(gè)寫(xiě)起來(lái)簡(jiǎn)介的代碼分享給大家。
看到表達(dá)式的形式，我們可以想到使用語(yǔ)法樹(shù)來(lái)解決，題目中限定了+號(hào)和-號(hào)的使用數(shù)目。但是對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，我們并不知道左子樹(shù)中有多少個(gè)+號(hào)和-號(hào)，也不知道右子樹(shù)中有多少個(gè)+號(hào)和-號(hào)。所以，就需要使用動(dòng)態(tài)規(guī)劃了。
對(duì)于每一可子樹(shù)，用一個(gè)vector <pair<int,int> > vec ,vec[i]來(lái)表示該子樹(shù)使用I個(gè)+號(hào)時(shí)候，表達(dá)式計(jì)算得到的最大、最小值。
遞推方法：
對(duì)于一個(gè)節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)的vec[t]vec[t]:
1.當(dāng)該節(jié)點(diǎn)采取+號(hào)時(shí)候，左子樹(shù)采取ll個(gè)+號(hào)，那么右子樹(shù)應(yīng)該采取t?l?1t?l?1個(gè)加號(hào)，
vec[t].first=max(vec[t].first,leftv[l].first+rightv[t?l?1].first);vec[t].first=max(vec[t].first,leftv[l].first+rightv[t?l?1].first);
vec[t].second=min(vec[t].second,leftv[l].second+rightv[t?l?1].second);vec[t].second=min(vec[t].second,leftv[l].second+rightv[t?l?1].second);
2.當(dāng)該節(jié)點(diǎn)采取-號(hào)的時(shí)候左子樹(shù)采取ll個(gè)加號(hào)，右子樹(shù)采取t?lt?l個(gè)加號(hào)，
vec[t].first=max(vec[t].first,leftv[l].first?rightv[t?l].second);vec[t].first=max(vec[t].first,leftv[l].first?rightv[t?l].second);
vec[t].second=min(vec[t].second,leftv[l].second?rightv[t?l].first);vec[t].second=min(vec[t].second,leftv[l].second?rightv[t?l].first);
最后注意不要越界，加入越界檢測(cè)

---

代碼

#include <iostream> #include <cstdio> #include <vector> using namespace std; const int inf = 1e7; typedef vector<pair<int,int> >vii; const int maxn = 1e4+7; char str[maxn]; int pos; vii expr(){char c = str[pos];if(c >= '0' && c <= '9'){++pos;vii v;v.push_back(make_pair(c-'0',c-'0'));return v;}++pos;vii v1 = expr();++pos;vii v2 = expr();++pos;int n1 = v1.size(),n2 = v2.size(),nn = n1+n2;vii res;for(int i = 0;i < nn;++i) res.push_back(make_pair(-inf,inf));//使用-號(hào)for(int i = 0;i < nn-1;++i){for(int j = 0;j <= min(i,n1-1);++j){if(i-j >= n2) continue;res[i].first = max(res[i].first,v1[j].first-v2[i-j].second);res[i].second = min(res[i].second,v1[j].second-v2[i-j].first);}}//使用+號(hào)for(int i = 0;i < nn;++i){for(int j = 0;j < min(i,n1);++j){if(i-j-1 >= n2) continue;res[i].first = max(res[i].first,v1[j].first+v2[i-j-1].first);res[i].second = min(res[i].second,v1[j].second+v2[i-j-1].second);} }return res; } int main(){int P,M;cin>>str>>P>>M;vii v = expr();cout<<v[P].first<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces 935E Fafa and Ancient Mathematics 语法树、动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。