数据结构与算法：dp优化——单调队列/单调栈优化
前言
最近又是牛客寒假营又是实验室集训的，都没时间点科技树了，好累……
前面几题感觉倒还好，基本读完题就能想到用窗口维护，而且 dp 的状态设计也不是很难，最后套个单调队列优化一下枚举即可。但最后的几个题就开始变态了，完全想不到一点……
一、琪露诺
byd因为设置成 -1 而不是 -INF 卡了半天，警钟长鸣……
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
* (= ._.)
* / > \>
*/
/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};
void solve()
{
int n,l,r;
cin>>n>>l>>r;
vector<int>a(n+1);
for(int i=0;i<=n;i++)
{
cin>>a[i];
}
//定义dp[i]为跳到i位置的最大值，那么就只能从前面[l,r]范围内的位置转移过来
//由于转移时肯定从范围内dp值最大的地方转移，所以可以使用单调队列维护窗口最大值
vector<int>dp(n+1,-INF);
dp[0]=a[0];
deque<int>q;
for(int i=1;i<=n;i++)
{
int cur=i-l;
int back=i-r-1;
//入窗口
if(cur>=0&&dp[cur]!=-INF)
{
while(!q.empty()&&dp[q.back()]<=dp[cur])
{
q.pop_back();
}
q.push_back(cur);
}
//出窗口
if(!q.empty()&&q.front()==back)
{
q.pop_front();
}
dp[i]=q.empty()?-INF:(dp[q.front()]+a[i]);
}
int ans=-INF;
for(int i=n-r+1;i<=n;i++)
{
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
void init()
{
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--)
{
solve();
}
return 0;
}首先，状态设计还是很简单的，考虑定义 dp[i] 为跳到 i 位置的最大值，那么就只能从前面 [l,r] 范围内的位置转移过来。因为这个范围很大，所以肯定不能每次都暴力枚举。又因为每次转移时肯定从范围内 dp 值最大的地方转移，所以可以使用单调队列维护窗口最大值。
二、Power 收集
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
* (= ._.)
* / > \>
*/
/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};
const int MAXN=4e3+5;
int n,m,k,t;
vector<vector<int>>dp(MAXN,vector<int>(MAXN));
void solve()
{
cin>>n>>m>>k>>t;
for(int i=1,x,y;i<=k;i++)
{
cin>>x>>y;
//直接用dp表作为原始值
cin>>dp[x][y];
}
//第一行就是自己
for(int i=2;i<=n;i++)
{
deque<int>q;
//初始窗口
for(int j=1;j<=t&&j<=m;j++)
{
while(!q.empty()&&dp[i-1][q.back()]<=dp[i-1][j])
{
q.pop_back();
}
q.push_back(j);
}
//滑动
for(int j=1;j<=m;j++)
{
if(j+t<=m)
{
while(!q.empty()&&dp[i-1][q.back()]<=dp[i-1][j+t])
{
q.pop_back();
}
q.push_back(j+t);
}
if(!q.empty()&&q.front()==j-t-1)
{
q.pop_front();
}
dp[i][j]+=dp[i-1][q.front()];
}
}
int ans=0;
for(int j=1;j<=m;j++)
{
ans=max(ans,dp[n][j]);
}
cout<<ans<<endl;
}
void init()
{
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--)
{
solve();
}
return 0;
}首先，第一行的答案肯定就是自己本身，在每次向下走时，能走的范围就是一个区间，那么也可以像上个题一样用单调队列维护窗口最大值。所以就是定义 dp[i][j] 为走到第 i 行第 j 列时的最大值，初始就用 dp 表作为整个网格的原始值。之后从第 2 行开始，每次维护一个单调队列，先扩窗口，然后再滑动更新即可。最后只需要考察一遍最后一行的每一列取最大值即可。
三、Mowing the Lawn G
难起来了……
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
* (= ._.)
* / > \>
*/
/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};
void solve()
{
int n,k;
cin>>n>>k;
vector<ll>a(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
//定义dp[i]为1~i范围上在不违规的情况下能获得的最大累加和
//那么当来到i位置时，前面最多要到i-k+1位置，i-k位置是必然不能要的
//那么此时的答案就是dp[i-k-1]+sum(i-k+1~i)
//以此类推，可以通过枚举哪里一定不要来进行转移
//观察dp[i-1]和dp[i]的公式，可以发现dp[i-k-1]+sum(i-k+1~i)可以用单调队列维护
//但当来到dp[i]时，所有的公式需要在后面加上a[i]，会发生变动
//Trick：对于每次发生变动的值，可以考虑通过前缀和转化成不变的形式
//所以公式可以转化为dp[i-k-1]-pre[i-k]+pre[i]
//那么维护dp[i-k-1]-pre[i-k]时，每次就是不变的了
vector<ll>pre(n+1);
for(int i=1;i<=n;i++)
{
pre[i]=pre[i-1]+a[i];
}
vector<ll>dp(n+1);
//不要i位置时要维护的值
auto value=[&](int i)->ll
{
return i==0?0:(dp[i-1]-pre[i]);
};
deque<int>q;
//不要0位置
q.push_back(0);
for(int i=1;i<=n;i++)
{
while(!q.empty()&&value(q.back())<=value(i))
{
q.pop_back();
}
q.push_back(i);
if(!q.empty()&&q.front()==i-k-1)
{
q.pop_front();
}
dp[i]=value(q.front())+pre[i];
}
cout<<dp[n]<<endl;
}
void init()
{
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--)
{
solve();
}
return 0;
}考虑定义 dp[i] 为 1~i 范围上在不违规的情况下能获得的最大累加和，那么当来到 i 位置时，前面最多要到 i-k+1 位置，i-k 位置是必然不能要的。那么此时的答案就是 dp[i-k-1]+sum(i-k+1~i)。以此类推，可以通过枚举哪里一定不要来进行转移。
观察 dp[i-1] 和 dp[i] 的公式，可以发现 dp[i-k-1]+sum(i-k+1~i) 可以用单调队列维护，但当来到 dp[i] 时，所有的公式需要在后面加上 a[i]，会发生变动。此时就涉及到一个 trick 了，那就是对于每次发生变动的值，可以考虑通过前缀和转化成不变的形式。所以公式可以转化为 dp[i-k-1]-pre[i-k]+pre[i]，那么维护 dp[i-k-1]-pre[i-k] 时，每次就是不变的了。
四、Fence
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
/* /\_/\
* (= ._.)
* / > \>
*/
/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};
const int MAXK=100+5;
const int MAXN=16000+5;
int n,k;
vector<int>L(MAXK),P(MAXK),S(MAXK);
vector<vector<int> >dp(MAXK,vector<int>(MAXN));
bool cmp(int x,int y)
{
return S[x]<S[y];
}
int value(int i,int p,int j)
{
return dp[i-1][j]-j*p;
};
void solve()
{
cin>>n>>k;
for(int i=1;i<=k;i++)
{
cin>>L[i]>>P[i]>>S[i];
}
//先对所有工人根据S[i]排序
//定义dp[i][j]为1~i范围上的工人在1~j范围上的木板工作，能获得的最大价值
//首先若i号工人不参与，那就是dp[i-1][j]，若参与但不刷j号木板，那就是dp[i][j-1]
//重点是i号工人参与且刷j号木板的情况
//若i号工人有L[i]=4，P[i]=3，S[i]=9
//首先，对于所有j<9的dp[i][j]，都不会有第三种情况
//对于dp[i][9]，最多只能刷6~9位置，所以就是dp[i-1][5]+4*3，之后以此类推
//对于dp[i][10]，最多只能刷7~10位置，所以就是dp[i-1][6]+4*3
//可以发现，该信息依然是变化的，所以同样考虑转化为前缀形式
//dp[i-1][6]+3*3可以转化为dp[i-1][6]-6*3+9*3
//dp[i-1][7]+4*3可以转化为dp[i-1][7]-7*3+10*3
//这样就可以用单调队列维护了
vector<int>id(k+1);
for(int i=1;i<=k;i++)
{
id[i]=i;
}
sort(id.begin()+1,id.end(),cmp);
for(int i=1,l,p,s;i<=k;i++)
{
l=L[id[i]];
p=P[id[i]];
s=S[id[i]];
deque<int>q;
//建立窗口
for(int j=max(0,s-l);j<s;j++)
{
while(!q.empty()&&value(i,p,q.back())<=value(i,p,j))
{
q.pop_back();
}
q.push_back(j);
}
//滑动
for(int j=1;j<=n;j++)
{
//前两种
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(j>=s)
{
if(!q.empty()&&q.front()==j-l-1)
{
q.pop_front();
}
if(!q.empty())
{
dp[i][j]=max(dp[i][j],value(i,p,q.front())+j*p);
}
}
}
}
cout<<dp[k][n]<<endl;
}
void init()
{
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--)
{
solve();
}
return 0;
}首先，对所有工人根据 S[i] 排序，然后考虑定义 dp[i][j] 为 1~i 范围上的工人在 1~j 范围上的木板工作，能获得的最大价值。那么首先就是若 i 号工人不参与，那么依赖的就是 dp[i-1][j]，若参与但不刷 j 号木板，那就是 dp[i][j-1]。重点是 i 号工人参与且刷 j 号木板的情况。
若 i 号工人有 L[i]=4，P[i]=3，S[i]=9。首先，对于所有 j<9 的 dp[i][j]，都不会有第三种情况，因为刷不到。之后，对于 dp[i][9]，最多只能刷 6~9 位置，所以其中一种就是从 6 刷到 9，那么转移就是 dp[i-1][5]+4*3，之后以此类推。对于 dp[i][10]，最多只能刷 7~10 位置，所以从 7 刷到 10 就是 dp[i-1][6]+4*3。可以发现，该信息依然是变化的，所以同样考虑转化为前缀形式。那么就是将 dp[i-1][5]+4*3 转化为 dp[i-1][5]-5*3+9*3，类似地将dp[i-1][6]+4*3 转化为 dp[i-1][6]-6*3+10*3，那么这样就可以用单调队列维护了。
五、最小移动总距离
class Solution {
public:
typedef long long ll;
const ll INF=1e18;
ll minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
int n=factory.size();
int m=robot.size();
//按位置从小到大排序
sort(robot.begin(),robot.end());
sort(factory.begin(),factory.end());
vector<vector<ll>>a(n+1,vector<ll>(2));
for(int i=1;i<=n;i++)
{
a[i][0]=factory[i-1][0];
a[i][1]=factory[i-1][1];
}
vector<ll>b(m+1);
for(int i=1;i<=m;i++)
{
b[i]=robot[i-1];
}
//定义dp[i][j]为前i个工厂负责前j个机器人的最小总距离
//举例可以发现，对于当前第i号工厂来说，因为已经排好序
//所以选择后面的机器人必然优于前面的机器人
//那么对于当前的dp[i][j]，如果不使用第i号工厂，那么就是dp[i-1][j]
//如果使用，若容量是k，那么就是枚举最后k个机器人中有几个来第i号工厂
//对于这个枚举行为，考虑构建前k号机器人来第i号工厂的前缀和数组
//那么就是dp[i][k]-pre[k]+pre[j]，就可以使用单调队列优化了
vector<vector<ll>>dp(n+1,vector<ll>(m+1));
//初始化
for(int j=1;j<=m;j++)
{
dp[0][j]=INF;
}
for(int i=1;i<=n;i++)
{
//前缀和
vector<ll>pre(m+1);
for(int j=1;j<=m;j++)
{
pre[j]=pre[j-1]+abs(b[j]-a[i][0]);
}
auto value=[&](int i,int j)->ll
{
if(dp[i-1][j-1]==INF)
{
return INF;
}
return dp[i-1][j-1]-pre[j-1];
};
deque<int>q;
for(int j=1;j<=m;j++)
{
//不工作
dp[i][j]=dp[i-1][j];
if(value(i,j)!=INF)
{
while(!q.empty()&&value(i,q.back())>=value(i,j))
{
q.pop_back();
}
q.push_back(j);
}
if(!q.empty()&&q.front()==j-a[i][1])
{
q.pop_front();
}
if(!q.empty())
{
dp[i][j]=min(dp[i][j],value(i,q.front())+pre[j]);
}
}
}
return dp[n][m];
}
};感觉这个题的转化和上个题差不多。
定义 dp[i][j] 为前 i 个工厂负责前 j 个机器人的最小总距离。举例可以发现，对于当前第 i 号工厂来说，因为已经排好序，所以选择后面的机器人必然优于前面的机器人。那么对于当前的 dp[i][j]，如果不使用第 i 号工厂，那么就是 dp[i-1][j]。而如果使用，若容量是 k，那么就是枚举最后 k 个机器人中有几个来第 i 号工厂。对于这个枚举行为，考虑构建前 k 号机器人来第 i 号工厂的前缀和数组，那么就是 dp[i][k]-pre[k]+pre[j]，就可以像上个题一样使用调队列优化了。
六、巫师的总力量和
没有人类了……
typedef long long ll;
template<class T>
constexpr T power(T a, ll b) {
T res = 1;
for (; b != 0; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
template<int M>
struct ModInt {
public:
constexpr ModInt() : x(0) {}
template<typename T>
constexpr ModInt(T x_) {
T v = x_ % M;
if (v < 0) {
v += M;
}
x = v;
}
constexpr int val() const {
return x;
}
constexpr ModInt operator-() const {
ModInt res;
res.x = (x == 0 ? 0 : M - x);
return res;
}
constexpr ModInt inv() const {
return power(*this, M - 2);
}
constexpr ModInt &operator*=(const ModInt &rhs) &{
x = ll(x) * rhs.val() % M;
return *this;
}
constexpr ModInt &operator+=(const ModInt &rhs) &{
x += rhs.val();
if (x >= M) {
x -= M;
}
return *this;
}
constexpr ModInt &operator-=(const ModInt &rhs) &{
x -= rhs.val();
if (x < 0) {
x += M;
}
return *this;
}
constexpr ModInt &operator/=(const ModInt &rhs) &{
return *this *= rhs.inv();
}
friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr bool operator==(ModInt lhs, const ModInt &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator<(ModInt lhs, const ModInt &rhs) {
return lhs.val() < rhs.val();
}
friend constexpr bool operator>(ModInt lhs, const ModInt &rhs) {
return lhs.val() > rhs.val();
}
friend constexpr bool operator<=(ModInt lhs, const ModInt &rhs) {
return lhs.val() <= rhs.val();
}
friend constexpr bool operator>=(ModInt lhs, const ModInt &rhs) {
return lhs.val() >= rhs.val();
}
friend constexpr bool operator!=(ModInt lhs, const ModInt &rhs) {
return lhs.val() != rhs.val();
}
friend constexpr std::istream &operator>>(std::istream &is, ModInt &a) {
ll i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt &a) {
return os << a.val();
}
private:
int x;
};
constexpr int M = 1e9+7;
using Z = ModInt<M>;
class Solution {
public:
int totalStrength(vector<int>& a) {
int n=a.size();
Z pre=a[0];
vector<Z>sumsum(n);
sumsum[0]=pre;
for(int i=1;i<n;i++)
{
pre+=a[i];
sumsum[i]=sumsum[i-1]+pre;
}
//单调栈
stack<int>stk;
Z ans=0;
for(int i=0;i<n;i++)
{
while(!stk.empty()&&a[stk.top()]>=a[i])
{
int cur=stk.top();
stk.pop();
int l=stk.empty()?-1:stk.top();
ans+=sum(l,cur,i,a,sumsum);
}
stk.push(i);
}
while(!stk.empty())
{
int cur=stk.top();
stk.pop();
int l=stk.empty()?-1:stk.top();
ans+=sum(l,cur,n,a,sumsum);
}
return ans.val();
}
//当前位置m，左侧第一个比它小的在l，右侧第一个比它小的在r
//sumsum为数组a前缀和的前缀和
//返回以a[m]为最小值的子数组，其累加和乘以最小值的结果
Z sum(int l,int m,int r,vector<int>&a,vector<Z>&sumsum)
{
Z left=sumsum[r-1];
if(m-1>=0)
{
left-=sumsum[m-1];
}
left*=(m-l);
Z right=0;
if(m-1>=0)
{
right+=sumsum[m-1];
}
if(l-1>=0)
{
right-=sumsum[l-1];
}
right*=(r-m);
return (left-right)*a[m];
}
};首先需要解决子数组最小值的问题。考虑从贡献法的角度入手，对于当前位置 i，其能作为最小值而产生贡献的子数组，最多也就能扩到其左右两侧第一个比它小的位置。举个例子，对于数组[6,2,3,4,4,1,5]，对于3位置的数字3，其能作为最小值产生贡献的子数组，最大就是子数组[3,4,4]。这个边界是由3位置左右两侧第一个比3小的数字2和1决定的。那么对于求左右两侧第一个比自己小的位置的这个问题，就可以通过单调栈来解决。对于相同的数字，也选择直接弹出，因为之后可以修正过来。举个例子，在数组[6,2,3,4,2,5]中，对于第一个2，在碰到第二个2时可以直接弹出结算。因为对于1~4、1~5这些子数组，是可以在结算第二个2时结算到的。
之后，由于遍历的复杂度就是O(n)的，所以需要做到在O(1)的时间里求出每个位置作为最小值产生贡献时，所有子数组的累加和。这里，对于求解所有子数组累加和这个问题，可以考虑通过构建前缀和的前缀和数组sumsum来解决。
举个例子，对于7位置的数，其左右两侧第一个比它小的位置分别在3和10位置。那么其能产生贡献的子数组有[4,7],[5,7],[6,7],[7,7]，[4,8],[5,8],[6,8],[7,8]，以及[4,9],[5,9],[6,9],[7,9]这些。那么首先，考虑sumsum[9]，其表示从[1,1]一直到[1,9]这些区间的累加和。之后，让其减去sumsum[6]，结果就是从[1,7]一直到[1,9]这三个区间的累加和。之后，让这个值乘以7-3=4，表示4份。然后，考虑sumsum[6]，其表示从[1,1]一直到[1,6]这些区间的累加和，再减去sumsum[2]，那么结果就是从[1,3]一直到[1,6]这四个区间的累加和，然后让其乘以10-7=3，表示3份。最后，让两者相减就是所有子数组的累加和。因为第一个值表示从[1,7]一直到[1,9]这三个区间每个取4份，对于[1,7]，这四份分别减去第二个值的四个区间，那么可以发现，结果正好是[4,7],[5,7],[6,7],[7,7]这四个子数组的累加和。以此类推，这样就可以求出所有产生贡献的子数组。
太逆天了这个思路……
七、子数组最大变序和
给定一个长度为n的数组arr，变序和的定义为：数组中每个值都可以减小或不变，必须把整体变成严格升序的。所有方案中，能得到的最大累加和，叫做数组的变序和。返回arr所有子数组的变序和中，最大的那个。1<=n,arr[i]<=10^6。
究竟是什么人能想出这个方法……
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
* (= ._.)
* / > \>
*/
/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};
//暴力解
ll solve1(int n,const vector<int>&a)
{
int maxx=0;
for(int i=1;i<=n;i++)
{
maxx=max(maxx,a[i]);
}
vector<vector<ll>>dp(n+1,vector<ll>(maxx+1,-1));
auto dfs=[&](auto &&self,int i,int p)->ll
{
if(p<=0||i==0)
{
return 0;
}
if(dp[i][p]!=-1)
{
return dp[i][p];
}
int cur=min(a[i],p);
ll nxt=self(self,i-1,cur-1);
ll ans=cur+nxt;
dp[i][p]=ans;
return ans;
};
ll ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,dfs(dfs,i,a[i]));
}
return ans;
}
//正解
ll solve2(int n,const vector<int>&a)
{
//定义dp[i]为子数组以i位置结尾，且i位置的数不变的最大变序和
//使用单调栈维护后续数字在向左贯穿时是否会导致值断崖式下降的可能性
//e.g. [70,200,120,100]
//从100开始往左，120需要被压成99，200需要被压成98
//但70无法跟98连起来，就称此时发生断崖式下降
//若栈顶数字大于等于当前数字，那么必然不会导致断崖式下降
//若栈顶数字小于当前数字
//若值差大于等于位差，说明从当前数字开始往左到栈顶位置必然会发生断崖式下降
//那么栈顶位置的数就不需要修改了，所以可以直接继承dp[stk.top()]
//若值差小于位差，说明从当前数字开始往左必然不会发生断崖式下降
//那么从当前位置到栈顶必然会呈现一个等差数列，这个是可以快速求出的
//之后，因为栈顶位置的数字必然会下降，那么就跳到栈顶位置，出栈顶，考虑栈里剩下元素
//因为在后续里，若此时的位置不会发生断崖，那么之前的位置也不会了
//等差数列累加和
auto sum=[&](int last,int n)->ll
{
n=min(last,n);
return (last*2-n+1)*n/2;
};
stack<int>stk;
vector<ll>dp(n+1);
ll ans=0;
for(int i=1;i<=n;i++)
{
int curIdx=i;
int curVal=a[curIdx];
while(curVal>0&&!stk.empty())
{
int topIdx=stk.top();
int topVal=a[topIdx];
if(topVal>=curVal)
{
stk.pop();
}
else
{
int loc=curIdx-topIdx;
ll val=curVal-topVal;
if(val>=loc)
{
dp[i]+=sum(curVal,loc)+dp[topIdx];
curVal=0;
curIdx=0;
break;
}
else
{
dp[i]+=sum(curVal,loc);
curVal-=loc;
curIdx=topIdx;
stk.pop();
}
}
}
//栈空了
if(curVal>0)
{
dp[i]+=sum(curVal,curIdx);
}
stk.push(i);
ans=max(ans,dp[i]);
}
return ans;
}
void test()
{
srand(time(0));
int n=100;
int v=100;
int testTime=50000;
cout<<"S"<<endl;
for(int i=1;i<=testTime;i++)
{
int sz=rand()%n+1;
vector<int>a(sz+1);
for(int i=1;i<=sz;i++)
{
a[i]=rand()%v+1;
}
ll ans1=solve1(sz,a);
ll ans2=solve2(sz,a);
if(ans1!=ans2)
{
cout<<"W"<<endl;
}
if(i%1000==0)
{
cout<<"Have Tested "<<i<<" Cases"<<endl;
}
}
cout<<"E"<<endl;
}
void init()
{
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--)
{
test();
}
return 0;
}首先，一个很常见的状态设计，就是定义dp[i]为子数组以i位置结尾，且i位置的数不变的最大变序和。之后，考虑使用单调栈维护后续数字在向左贯穿时是否会导致值断崖式下降的可能性。举个例子，对于数组[70,200,120,100]，从100开始往左，120需要被压成99，200需要被压成98，但70无法跟98连起来，就称此时发生断崖式下降。
之后分类讨论，首先，若栈顶数字大于等于当前数字，那么必然不会导致断崖式下降，因为栈顶数字永远可以跟在当前数字后面，那么就可以直接pop栈顶了。
而若栈顶数字小于当前数字，若值差大于等于位差，说明从当前数字开始往左到栈顶位置必然会发生断崖式下降。因为若当前数字不变，中间数字会一直递减。来到栈顶位置时，这个数是会小于前一个数的。那么栈顶位置的数就不需要修改了，所以可以直接继承dp[stk.top()]。否则，即值差小于位差，说明从当前数字开始往左必然不会发生断崖式下降，即当中间数字递减到栈顶位置时，这个数会大于等于前一个数。那么从当前位置到栈顶必然会呈现一个等差数列，这个是可以快速求出的。之后，因为栈顶位置的数字必然会下降，那么就跳到栈顶位置，出栈顶，然后考虑栈里剩下元素。因为在后续里，若此时的位置不会发生断崖，那么之前的位置也不会了。
八、从仓库到码头运输箱子
class Solution {
public:
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n=boxes.size();
//定义dp[i]为送完前i个货物最少的行程数
//暴力方法
//对于当前位置i，只需要计算最后一轮能装哪些货，然后依赖前面的dp即可
//那么最后一轮能装的货，可以使用窗口维护，那么用单调队列就可以维护可能性
//贪心优化
//首先，dp[i]存在单调性，因为送i个货的行程必然小于等于送i+1个货
//之后，最后一轮送i~j范围上的货的行程cost也具有单调性
//cost在计算时，只需要当前数和前一个数不同，那么行程就需要+1
//所以，当范围变小时，cost要么不变要么变小
//所以对于当前窗口，若让最左侧的货l和之前的一起送，存在dp[l]==dp[l+1]
//那么肯定是让这个货之前送，因为这样可以缩小当前窗口cost的范围
//若最左侧的货l和之前的一起送，存在dp[l]<dp[l+1]，那么就不让其和前面的一起送了
//证明
//若0~l-1的轮数和0~l的轮数一样，那么就会导致行程+1
//又因为把第l号货物放到之前，最多只会导致当前轮的行程数-1
//所以是不会产生增益的
//若0~l-1的轮数小于0~100的轮数，因为出一次回一次都+2了，那么就会导致+(>1)
//所以若存在dp[l]<dp[l+1]，那么就不让l和前面一起了
vector<int>dp(n+1);
//初始化：只送一个货物去一次回一次
dp[1]=2;
//最后一轮的总重量
int sum=boxes[0][1];
int trip=2;
for(int l=0,r=1;r<n;r++)
{
sum+=boxes[r][1];
if(boxes[r][0]!=boxes[r-1][0])
{
trip++;
}
//最后一轮超限制了 或 可以把左侧货物往前放
while(r-l+1>maxBoxes||sum>maxWeight||dp[l]==dp[l+1])
{
sum-=boxes[l++][1];
if(boxes[l][0]!=boxes[l-1][0])
{
trip--;
}
}
dp[r+1]=dp[l]+trip;
}
return dp[n];
}
};首先，定义dp[i]为送完前i个货物最少的行程数。
先说暴力方法，就是对于当前位置i，只需要计算最后一轮能装哪些货，然后依赖前面的dp即可。那么最后一轮能装的货可以使用窗口维护，那么用单调队列就可以维护可能性。
之后，这个思路其实是可以用贪心优化的。首先，dp[i]存在单调性，因为送i个货的行程必然小于等于送i+1个货。之后，可以发现，最后一轮送i~j范围上的货的行程cost也具有单调性。因为cost在计算时，只需要当前数和前一个数不同，那么行程就需要+1。所以，当范围变小时，cost要么不变要么变小。
所以贪心策略就是，对于当前窗口，若让最左侧的货l和之前的一起送，存在dp[l]==dp[l+1]。那么肯定是让这个货之前送，因为这样可以缩小当前窗口cost的范围。若最左侧的货l和之前的一起送，存在dp[l]<dp[l+1]，那么就不让其和前面的一起送了。
证明如下：若0~l-1的轮数和0~l的轮数一样，那么就会导致行程+1。又因为把第l号货物放到之前，最多只会导致当前轮的行程数-1，所以是不会产生增益的。而若0~l-1的轮数小于0~100的轮数，因为出一次回一次都+2了，那么就会导致+(>1)。所以若存在dp[l]<dp[l+1]，那么就不让l和前面一起了。
总结
后面这几个题太难了……
END
更多推荐
17
0- 0
已为社区贡献2条内容
所有评论(0)