洛谷 P5858 「SWTR-03」Golden Sword

题目链接: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\))
洛谷 P5858 「SWTR-03」Golden Sword
如上图,对于固定的\(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]\)都在单调队列中。

上一篇:Vasya and Golden Ticket


下一篇:P5858 Golden Swold