题目链接:https://www.luogu.com.cn/problem/P5858
朴素算法(45分):
状态表示:\(dp[i][t]\)表示将前i个物品放入锅中,包括第i个物品在内锅中一共含有t个物品的最大耐久度。
状态计算:
\(dp[i][t] = max(dp[i - 1][l] + t*a[i], dp[i][t])\)
其中\(t-1 <=l<= min(w, t + s-1,i-1)\)
\(1<=t<=min(i,w)\)
具体含义:将第\(i\)个放入锅之前锅内有\(l\)件材料,如果什么都不取出,那么\(l=t-1\),直接放第\(i\)件,此时为\(dp[i-1][t-1]+t*a[i]\),当然也可以取出若干件材料,记取出件数为\(r\),那么\(l-r = t-1\),根据\(r<=s\)可知\(l<=t+s-1\).又因为锅内至多放下\(w\)件,并且前面至多有\(i-1\)件材料,故而总的来说有:t-1 <=l<= min(w, t + s-1,i-1)
注意:最后枚举答案时,由于放入第\(n\)件材料之后锅内的材料数目不确定,所以进行枚举取最大。
代码:
#include<bits/stdc++.h>
using namespace std;
#define inf LLONG_MAX
typedef long long int ll;
const int N = 5005;
int n, w, s;
ll dp[N][N];
int a[N];
int main()
{
cin>>n>>w>>s;
for(int i = 1;i <= n; i++)cin>>a[i];
//求最大值初始化为最小值
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= w;j++)
{
dp[i][j] = -inf;
}
}
dp[1][1] = a[1];//放入第一件材料
for(int i = 2;i <= n; i++)
{
for(int t = min( i, w );t >= 1; t--)
{
for(int l = min(i - 1, min(t + s - 1, w) ); l >= t - 1; l--)
{
dp[i][t] = max(dp[i][t],dp[i - 1][l] + (ll)t*a[i]);
}
}
}
ll ans = -inf;
for(int i = 1;i <= w; i++)ans = max(ans, dp[n][i]);
cout<<ans;
return 0;
}
单调队列优化(AC)
为什么这里会用到单调队列?
我们观察到上面代码第三重循环实际上求的是某一个区间\([t-1, min(w, t + s-1,i-1)]\)上的最大值,而且随着t的变化,这个区间就像一个滑动窗口一样进行变化。
类似于滑动窗口那一道题,这里的区间与\(t\)相关联。(窗口长度不超过\(s+1\))
如上图,对于固定的\(i\),我们在减小\(t\)的时候,实际上是\(dp[i-1][l]\)所对应的窗口向右滑动。
采用类似与滑动窗口一题的思想,我们得到以下优化:
#include<bits/stdc++.h>
using namespace std;
#define inf LLONG_MAX>>1
typedef long long int ll;
const int N = 5005;
int n, m, s;
ll dp[N][N], q[N];
int a[N], pos[N];
int main()
{
cin>>n>>m>>s;
for(int i = 1;i <= n; i++)cin>>a[i];
//求最大值初始化为最小值
for(int i = 0;i <= n; i++)
for(int j = 0;j <= m;j++)
dp[i][j] = -inf;
dp[0][0] = 0;
for(int i = 1; i <= n; i++)
{
int l = 1, r = 1;
pos[l] = m;
q[pos[l]] = dp[i - 1][m];
for(int t = m; t >= 1; t--)
{
while(pos[l] >= t + s&&l <= r)++l;//对应上图区间(窗口)右移
while(q[pos[r]] < dp[i - 1][t - 1]&&l <= r)--r;//将dp[i-1][t-1]插入合适位置
pos[++r] = t - 1;
q[pos[r]] = dp[i-1][t-1];
//每次队列左端即为最大值
dp[i][t] = q[pos[l]] + (ll)t*a[i];
}
}
ll ans = -inf;
for(int i = 1;i <= m; i++)ans = max(ans, dp[n][i]);
cout<<ans;
return 0;
}
注意点:\(pos[]\)是允许不连续的,这是因为并非每一个\(dp[i-1][x]\)都在单调队列中。