集团网站建设制作费用,网站制作怎么学,互联网产品经理,动态手机网站怎么做的题解 一道很有意思的题目#xff0c;同时把动态规划和语法树结合起来#xff0c;很有新意#xff0c;思路我是想出来了#xff0c;但是我的写法较为麻烦#xff0c;从别人的submission中找了一个写起来简介的代码分享给大家。 看到表达式的形式#xff0c;我们可以想到使…题解 一道很有意思的题目同时把动态规划和语法树结合起来很有新意思路我是想出来了但是我的写法较为麻烦从别人的submission中找了一个写起来简介的代码分享给大家。 看到表达式的形式我们可以想到使用语法树来解决题目中限定了号和-号的使用数目。但是对于一个节点来说我们并不知道左子树中有多少个号和-号也不知道右子树中有多少个号和-号。所以就需要使用动态规划了。 对于每一可子树用一个vector pairint,int vec ,vec[i]来表示该子树使用I个号时候表达式计算得到的最大、最小值。 递推方法 对于一个节点计算该节点的vec[t]vec[t]vec[t]: 1.当该节点采取号时候左子树采取lll个+号，那么右子树应该采取t#x2212;l#x2212;1" role="presentation" style="position: relative;">t−l−1t−l−1t-l-1个加号 vec[t].firstmax(vec[t].first,leftv[l].firstrightv[t−l−1].first);vec[t].firstmax(vec[t].first,leftv[l].firstrightv[t−l−1].first);vec[t].first = max(vec[t].first,leftv[l].first+rightv[t-l-1].first); vec[t].secondmin(vec[t].second,leftv[l].secondrightv[t−l−1].second);vec[t].secondmin(vec[t].second,leftv[l].secondrightv[t−l−1].second);vec[t].second = min(vec[t].second,leftv[l].second+rightv[t-l-1].second); 2.当该节点采取-号的时候左子树采取lll个加号，右子树采取t#x2212;l" role="presentation" style="position: relative;">t−lt−lt-l个加号 vec[t].firstmax(vec[t].first,leftv[l].first−rightv[t−l].second);vec[t].firstmax(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].secondmin(vec[t].second,leftv[l].second−rightv[t−l].first);vec[t].secondmin(vec[t].second,leftv[l].second−rightv[t−l].first);vec[t].second = min(vec[t].second,leftv[l].second-rightv[t-l].first); 最后注意不要越界加入越界检测 代码
#include iostream
#include cstdio
#include vector
using namespace std;
const int inf 1e7;
typedef vectorpairint,int vii;
const int maxn 1e47;
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 n1n2;vii res;for(int i 0;i nn;i) res.push_back(make_pair(-inf,inf));//使用-号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);}}//使用号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].firstv2[i-j-1].first);res[i].second min(res[i].second,v1[j].secondv2[i-j-1].second);} }return res;
}
int main(){int P,M;cinstrPM;vii v expr();coutv[P].firstendl;return 0;
}
