P5858 「SWTR-03」Golden Sword - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
理解题意后，我们知道贪心和暴力枚举显然是不行的，联想到DP
我们设置dp[i][j]表示,第 i 种原料加入后，锅里一共有 j 个原料
再看题意：所幸的是，每放入一个原料之前，小 E 可以从中取出一些原料，数量不能超过 s 个。
所以在加入这种材料之前，锅里一共放如过 i-1 种原料，锅里一共有的原料范围 [ j-1, ,min(j+s-1,w) ]
所以DP转移方程为:dp[i][j] = max( dp[i-1][k]+a[i]*j ) k∈ [ j-1, ,min(j+s-1,w) ]
由于是有负数的可能，所以一开始我们把所有的dp原始初值令为-1e18,而dp[0][0]应该为0
45分Code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back //vector函数
#define popb pop_back //vector函数
#define fi first
#define se second
const int N=5010;
//const int M=;
//const int inf=0x3f3f3f3f; //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int T,n,w,s;
ll a[N],dp[N][N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
n=read(),w=read(),s=read();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) dp[i][j]=-1e18;
dp[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=w;j++)
for(int k=0;k<=s&&j+k-1<=w;k++) dp[i][j]=max(dp[i][j],dp[i-1][j+k-1]+a[i]*j);
ll ans=-1e18;
for(int i=1;i<=w;i++) ans=max(ans,dp[n][i]);
printf("%lld",ans);
return 0;
}
再来看DP转移方程：
DP转移方程为:dp[i][j] = max( dp[i-1][k]+a[i]*j ) k∈ [ j-1, ,min(j+s-1,w) ]
dp[i][j]=max(dp[i-1][k])+a[i]*j; k∈ [ j-1, ,min(j+s-1,w) ]
只要优化取 max(dp[i-1][k]) k∈ [ j-1, ,min(j+s-1,w) ]即可。
对于这个，我们可以建一个单调队列用来维护 dp[i-1]，而范围就是[ j-1, ,min(j+s-1,w) ]，这就是 移动窗口模板
简单讲一下单调队列：一般用于维护移动的下标[L,R]之间的最值。
用到的deque是用来存队列的下标的
新建一个cnt, 用于表示选到了哪个数，一般来说cnt=0，这个cnt表示第一个没有取到的数；
如果cnt<=R,那么就把 cnt 加入队尾back，显然这还不够，还要保持单调性，（把队尾所有 小于等于 或 大于等于 cnt的全都pop_back() // 如果队列为空，直接加入）
那么队尾就操作好了。
而我们每次取数,取下标[L,R]中的最值，是从队头front取的。
显然队里的所有下标都是满足<=R的，所有我们只需让所有小于L的队头pop_front()就好了
单调队列的特点就是 ： 先把小于<=R的数加入，再剔除<L的数，最后取队头
最终我们用队头进行DP转移
但是，无论何时何刻，我们都要保证要用队头时，队不是空的
此题单调队列的代码：
deque<int> q;
int cnt=0;
for(int j=1;j<=w;j++)
{
for(;cnt<=min(w,j+s-1);cnt++) 如果cnt<=R,那么就把 cnt 加入队尾back，显然这还不够，还要保持单调性，（把队尾所有 小于等于 或 大于等于 cnt的全都pop_back() // 如果队列为空，直接加
{
if(q.empty()) q.pb(cnt);
else
{
while(!q.empty()&&dp[i-1][q.back()]<=dp[i-1][cnt]) q.pop_back();
q.pb(cnt);
}
}
while(!q.empty()&&q.front()<j-1 ) q.pop_front(); 显然队里的所有下标都是满足<=R的，所有我们只需让所有小于L的队头pop_front()就好
if(!q.empty()) dp[i][j]=dp[i-1][q.front()]+a[i]*j;但是，无论何时何刻，我们都要保证要用队头时，队不是空的
}
100分Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back //vector函数
#define popb pop_back //vector函数
#define fi first
#define se second
const int N=5010;
//const int M=;
//const int inf=0x3f3f3f3f; //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int T,n,w,s;
ll a[N],dp[N][N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
n=read(),w=read(),s=read();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) dp[i][j]=-1e18;
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
deque<int> q;
int cnt=0;
for(int j=1;j<=w;j++)
{
for(;cnt<=min(w,j+s-1);cnt++)
{
if(q.empty()) q.pb(cnt);
else
{
while(!q.empty()&&dp[i-1][q.back()]<=dp[i-1][cnt]) q.pop_back();
q.pb(cnt);
}
}
while(!q.empty()&&q.front()<j-1 ) q.pop_front();
if(!q.empty()) dp[i][j]=dp[i-1][q.front()]+a[i]*j;
// for(int k=j-1;k<=min(w,j+s-1);k++) dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i]*j);
}
}
ll ans=-1e18;
for(int i=1;i<=w;i++) ans=max(ans,dp[n][i]);
printf("%lld",ans);
return 0;
}
最后放个55分用堆来写单调队列的DPCode：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back //vector函数
#define popb pop_back //vector函数
#define fi first
#define se second
const int N=5010;
//const int M=;
//const int inf=0x3f3f3f3f; //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int T,n,w,s;
ll a[N],dp[N][N];
struct node
{
int id;ll v;
friend bool operator < (const node &a,const node &b)
{
return a.v<b.v;
}
};
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
n=read(),w=read(),s=read();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) dp[i][j]=-1e18;
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
priority_queue<node> q;
int cnt=0;
for(int j=1;j<=w;j++)
{
for(;cnt<=min(w,j+s-1);cnt++) q.push(node{cnt,dp[i-1][cnt]});
while(!q.empty()&& q.top().id<j-1 ) q.pop();
if(!q.empty()) dp[i][j]=q.top().v+a[i]*j;
// for(int k=j-1;k<=min(w,j+s-1);k++) dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i]*j);
}
}
ll ans=-1e18;
for(int i=1;i<=w;i++) ans=max(ans,dp[n][i]);
printf("%lld",ans);
return 0;
}
标签：03,ch,const,Golden,int,ll,SWTR,dp,define From： https://www.cnblogs.com/Willette/p/17068201.html