arc067f

题意：一条路上有n个店，有m张票，票i可以在店j获得$$d_{ji}$$的收益，从店i走到店i+1有$$a_i$$的花费。求从任意一个店开始能获得的最大收益。

一定不会走重复的路径
暴力：对于每一张票j，求每一家店的最大值覆盖区间，设店i的区间为[L[i],R[i]]，那么将起点在[L[i],i]终点在[i,R[i]]的路径$$+d_{ij}$$,用二维树状数组维护，小范围暴力

#include <bits/stdc++.h>
using namespace std;
#define M 210
#define N 5100
#define ll long long
const int bnd = 200;
int n,m,top;
int a[N],b[M][N],st[N],L[M][N],R[M][N];
ll sum[N],tr[N][N],ans;
void insert(int x,int y,int v)
{
    for(int i=x;i;i-=i&-i)
        for(int j=y;j;j-=j&-j)
            tr[i][j]+=v;    
}
ll query(int x,int y)
{
    ll ret=0;
    for(int i=x;i<=n;i+=i&-i)
        for(int j=y;j<=n;j+=j&-j)
            ret+=tr[i][j];
    return ret;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[j][i]);
    for(int i=1;i<=m;i++)
    {
        top=0;st[top]=0;
        for(int j=1;j<=n;j++)
        {
            while(top&&b[i][j]>b[i][st[top]])top--;
            L[i][j]=st[top]+1;
            st[++top]=j;
        }
        top=0;st[top]=n+1;
        for(int j=n;j>=1;j--)
        {
            while(top&&b[i][j]>=b[i][st[top]])top--;
            R[i][j]=st[top]-1;
            st[++top]=j;
        }
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if((j-L[i][j]+1)*(R[i][j]-j+1)>=bnd)
            {
                insert(j,R[i][j],b[i][j]);
                insert(L[i][j]-1,j-1,b[i][j]);
                insert(L[i][j]-1,R[i][j],-b[i][j]);
                insert(j,j-1,-b[i][j]);
            }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            tr[i][j]=query(i,j);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if((j-L[i][j]+1)*(R[i][j]-j+1)<bnd)
            {
                for(int k=L[i][j];k<=j;k++)
                    for(int w=j;w<=R[i][j];w++)
                        tr[k][w]+=b[i][j];
            }
    for(int i=1;i<n;i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            ans=max(ans,tr[i][j]-(sum[j-1]-sum[i-1]));
    printf("%lld\n",ans);
    return 0;
}

正解：设以i为起点的最优路径终点为p[i]，那么随着i的递增p[i]单调不减。因此可以rmq预处理，设solve(l1,r1,l2,r2)表示求解起点在[l1,r1]内终点可行区间为[l2,r2]的路径。然后求出l1,r1中点mid的最优路径终点，递归处理。

#include <bits/stdc++.h>
using namespace std;
#define M 210
#define N 5100
#define ll long long
int n,m;
int a[N],b[M][N],mx[M][N][16],bir[N];
ll sum[N],ans;
int query(int x,int l,int r)
{
    int t=bir[r-l+1];
    return max(mx[x][l][t],mx[x][r-(1<<t)+1][t]);
}
void solve(int l1,int r1,int l2,int r2)
{
    if(l1>r1)return;
    int mid=(l1+r1)>>1;
    ll v=0,p=max(l2,mid);
    for(int i=max(l2,mid);i<=r2;i++)
    {
        ll t=0;
        for(int j=1;j<=m;j++)
            t+=query(j,mid,i);
        t-=sum[i-1]-sum[mid-1];
        if(t>v)v=t,p=i;
    }
    ans=max(ans,v);
    solve(l1,mid-1,l2,p);
    solve(mid+1,r1,p,r2);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[j][i]);
    bir[1]=0;
    for(int i=2;i<=n;i++)
        bir[i]=bir[i>>1]+1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)mx[i][j][0]=b[i][j];
        for(int j=1;j<=bir[n];j++)
            for(int k=1;k+(1<<j)-1<=n;k++)
                mx[i][k][j]=max(mx[i][k][j-1],mx[i][k+(1<<j-1)][j-1]);
    }
    solve(1,n,1,n);
    printf("%lld\n",ans);
    return 0;
}