欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  web前端

Codeforces Round #271 (Div. 2) E题 Pillars（线段树维护DP）_html/css_WEB-ITnose

程序员文章站 2022-04-14 11:48:44
...
题目地址：http://codeforces.com/contest/474/problem/E

第一次遇到这种用线段树来维护DP的题目。ASC中也遇到过，当时也很自然的想到了线段树维护DP，但是那题有简单方法，于是就没写。这次终于写出来了。。

这题的DP思想跟求最长上升子序列的思想是一样的。只不过这里的找前面最大值时会超时，所以可以用线段树来维护这个最大值，然后由于还要输出路径，所以要用线段树再来维护一个每个数在序列中所在的位置信息。

手残了好多地方，终于调试出来了。。。

代码如下：

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL __int64#define lson l, mid, rt=maxv[rt>1;    if(p=r)    {        if(q_maxv>1, ans=0;    if(llmid) query(ll,rr,rson);}int bin_seach(LL x){    int low=0, high=cnt-1, mid;    while(low>1;        if(d[mid]==x) return mid;        else if(d[mid]>x) high=mid-1;        else low=mid+1;    }}int l_seach(LL x){    int low=0, high=cnt-1, mid, ans=-1;    while(low>1;        if(d[mid]>1;        if(d[mid]>=x)        {            ans=mid;            high=mid-1;        }        else low=mid+1;    }    return ans;}void print(int x){    if(x==-1) return ;    print(pre[x]);    printf("%d ",x+1);}int main(){    int n, dd, i, x, ans, y, z, max1=-1, pos, tot;    scanf("%d%d",&n,&dd);    for(i=0; i
相关标签： Codeforces Round #271 (Div. 2) E题 Pillars（线段树维护DP）

上一篇： 有关php的异常

下一篇： css动画制作——CSS animate

推荐阅读