P1725 琪露诺

· · 题解

这个题朴素的dp思想很好想，大体可以应用一下数字三角形的思想

从后往前推，对于每个点i，它可以跳到i+L到i+R中的任意一格

假设我们在跳往i的路上走的是最优路，那么我们下一步一定要跳到

价值最大的那个格子上，即A[i]=max{A[i+L]...A[i+R]}+dt[i];

而这样的话我们的时间复杂度就是O(n*(R-L))的，看一眼数据范围发现只能拿60分

那么我们就可以想了，怎么快速的找到A[i+L]到A[i+R]中最大的那一个呢？

单调队列，优先队列，线段树均可

以下给出线段树的做法

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dt[200001];
int A[2000001];
int n,L,R,ans=0;
int maxx=-10101000,from;
struct Tree
{
    int l;
    int r;
    int v;
    int add;
};
struct Tree T[200001*4];
void buildtree(int f,int ne,int poi)//建树 
{
    T[poi].l=f;
    T[poi].r=ne;
    if(f==ne)
    {
        T[poi].v=0;
        T[poi].add=f;  //用来存该区间最大数在原序列的位置 
        return ;
    }
    buildtree(f,(f+ne)/2,poi*2);
    buildtree((f+ne)/2+1,ne,poi*2+1);
    if(T[poi*2].v>T[poi*2+1].v)
    {
        T[poi].v=T[poi*2].v;
        T[poi].add=T[poi*2].add;
    }
    else
    {
        T[poi].v=T[poi*2+1].v;
        T[poi].add=T[poi*2+1].add;
    }
}
void insert(int go,int val,int poi)  //修改值（单点修改） 
{
    //printf("%d %d %d\n",go,val,poi);
    if(T[poi].l==go&&T[poi].r==go)
    {
        T[poi].v=val;
        return ;
    }
    int mid=(T[poi].l+T[poi].r)/2;
    if(go>mid) insert(go,val,poi*2+1);
    else insert(go,val,poi*2);
    if(T[poi*2].v>T[poi*2+1].v)
    {
        T[poi].v=T[poi*2].v;
        T[poi].add=T[poi*2].add;
    }
    else
    {
        T[poi].v=T[poi*2+1].v;
        T[poi].add=T[poi*2+1].add;
    }
}
void search(int f,int ne,int poi)  //查询区间最大值 
{
    if(T[poi].l==f&&T[poi].r==ne)
    {
        if(T[poi].v>maxx)
        {
            maxx=T[poi].v;    //区间最大值 
            from=T[poi].add;  //区间最大值的位置 
        }
        return ;
    }
    int mid=(T[poi].l+T[poi].r)/2;
    if(f>mid) search(f,ne,poi*2+1);
    else if(ne<=mid) search(f,ne,poi*2);
    else
    {
        search(f,mid,poi*2);
        search(mid+1,ne,poi*2+1);
    }
}
void dp()
{
    for(int i=n;i>=0;i--)
    {
        from=-1;
        maxx=-10101001;
        search(i+L,i+R,1);   //去找i+L到i+R中的最大值 
        A[i]=A[from]+dt[i];
        insert(i,A[i],1);  //用更新后的值去修改原来的值 
    }
}
void print()
{
    for(int i=0;i<=n+R;i++)
    {
        printf("%d ",A[i]);
    }
}
int main()
{
    scanf("%d%d%d",&n,&L,&R);
    for(int i=0;i<=n;i++)
    {
        scanf("%d",&dt[i]);
    }
    for(int i=n+1;i<=n+R;i++)
    {
        dt[i]=0;
    }
    buildtree(0,n+R,1);
    dp();
    //print();
    printf("%d",A[0]);  //因为起点是0号点 A[0]就表示从0号点出发的最大价值 
    return 0;
}
/*void dp()  //朴素dp（60分） 
{
    for(int i=n;i>=0;i--)
    {
        for(int j=L;j<=R;j++)
        {
            A[i]=max(A[i+j]+dt[i],A[i]);
        }
    }
}*/

RP++