codeforces 1101F Trucks and Cities 区间dp+单调优化 好题

题目传送门

题意简述：（来自洛谷）

有n个城市坐落在一条数轴上，第ii个城市位于位置ai?．

城市之间有m辆卡车穿行．每辆卡车有四个参数：si?为起点编号，fi?为终点编号，ci?表示每行驶1个单位长度需要消耗的油量，ri?表示可以在路途中加油的次数．

当卡车到达一个城市的时候可以将油加满（当然也可以不加），在路中无法加油，但是路途中总加油次数不能超过ri?．

所有卡车的油箱都是一样大的，我们称它的容积为V．试求一个最小的V，使得对于所有的卡车都存在一种方案，在路途中任意时刻油箱内的油量大于等于0且路途中总加油次数小于等于ri?的情况下从起点城市到达终点城市．

n,m(n≤400,m≤250000)表示城市数量与卡车数量。

思路：

　　此题学习了洛谷的博客，但洛谷的博客有地方是错误的，导致自闭了许久，自己证明了一波，才走出自闭。

　　洛谷题解 点这里   但是洛谷题解有错，并且最重要的单调性没有证明。

　　首先，主体是一个区间DP

　　设 dp{i,j,k}? 为：从第 i 个城市到第 j 个城市分成 k 段，这 k 段中长度最大的一段的最小值

　　边界： dp{i,j,0}=aj-ai(1≤i≤j≤n)。

　　状态转移方程

　　dp {i,j,k}=dp{i,j,k}?=min（? (max(dp{i,w,k?1}?,aj??aw?))(0<k≤n)）( i <= w <= j )

　　目标：max?(ci*?dp{si?,fi?,ri?}?)  i<=m

      以上均取自洛谷，并且洛谷的状态转移方程还写错了。上面这个区间dp的时间复杂度是O（n⁴）的，显然会超时，要进行优化，洛谷题解中说单调性是显然得出的，，然而我证明了好久。

      先说两个结果：

　　1）当 k,i 确定， j 在不断向右移时，对每个 j 取到的 w 具有单调性。

　　2）同时，当 j 确定时，不同的 w 对应的取值呈“先减后增” 的趋势，

　　我们先证明第二点，当i j k 确定时，转移方程中  我们设dp{i,w,k?1}?为 Aw，aj??aw? 为Bw，当w变大时，Aw可能变大，Bw必定变小，所以取值一开始肯定是取Bw的，慢慢变的有可能取Aw，可以想象，这个dp方程一开始肯定是w越大越好，但是当某一个临界点，如果比前面大了，那我们会发现，此时的最大值必定不是Bw，因为Bw<B(w-1)，这是必定的。所以最大值是Aw，而w越大，Aw则可能变大，但绝不变小，所以不会有变小的趋势了，证毕。

　　然后证明第一点，假设j‘=j+1，我们先看w是否会前移。发现j变成j‘后，只有Bw会变大，Aw是不变的，而越往后的项，最大值取Aw的可能性越大，所以前面的项只会变大，就算当前项变大了，那变大的程度也会和前面的一样，所以取最小值的话当前w必定由于小于w的值。

　　那么看w是否会后移，由于Bw会变大，Aw只是可能变大，后面的项比前面的项更有可能用到Aw，所以后面的项可能更优，w可能后移，有单调性，证毕。

　　注意不要开数组不要long long，会爆内存，也不要开太大，开了410*410*410会mle。

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll; 
const int maxn=402;
ll ans;
int dp[maxn][maxn][maxn],a[maxn];
int n,m;
int main(){
    while(cin>>n>>m)
    {
        ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                dp[i][j][0]=a[j]-a[i];
            }
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                int w=i;
                for(int j=i;j<=n;j++)
                {
                    while(w<j&&max(dp[i][w][k-1],a[j]-a[w])>max(dp[i][w+1][k-1],a[j]-a[w+1]))w++;
                    dp[i][j][k]=max(dp[i][w][k-1],a[j]-a[w]);
                }
            }
        }
        int s,f,r;
        ll c;
        while(m--)
        {
            scanf("%d%d%lld%d",&s,&f,&c,&r);
            ans=max(ans,dp[s][f][r]*c);
        }
        cout<<ans<<endl;
    }
} 

View Code

codeforces 1101F Trucks and Cities 区间dp+单调优化 好题

原文：https://www.cnblogs.com/mountaink/p/10350385.html