【原题】
题目背景
小 E 不幸在一场战斗中失去了他的金宝剑。
题目描述
制造一把金宝剑需要 (n)种原料，编号为 (1) 到 (n)，编号为 (i) 的原料的坚固值为 (a_i)。
炼金是很讲究放入原料的顺序的，因此小 E必须按照 (1) 到 (n) 的顺序依次将这些原料放入炼金锅。
但是，炼金锅的容量非常有限，它最多只能容纳 (w)个原料。
所幸的是，每放入一个原料之前，小E可以从中取出一些原料，数量不能超过 (s) 个。
- 我们定义第 iii 种原料的耐久度为：放入第 (i) 种原料时锅内的原料总数 (×a_i)，则宝剑的耐久度为所有原料的耐久度之和。
小 Emathrm{E}E 当然想让他的宝剑的耐久度尽可能得大，这样他就可以带着它进行更多的战斗，请求出耐久度的最大值。
注：这里的“放入第 iii 种原料时锅内的原料总数包括正在放入锅中的原料，详细信息请见样例。
输入格式
第一行，三个整数 (n, w, s)。
第二行，(n)个整数 (a_1,a_2,…,a_n)。
输出格式
一行一个整数，表示耐久度的最大值。
输入输出样例
输入 #1
5 3 3
1 3 2 4 5
输出 #1
40
输入 #2
5 3 3
1 -3 -2 4 5
输出 #2
21
输入 #3
7 4 2
-5 3 -1 -4 7 -6 5
输出 #3
17
输入 #4
5 3 1
-1 -3 -2 -4 -5
输出 #4
-15
【思路】
确定上一层可转移到当前状态的范围，取最大值即可，取最大值用单调队列优化。
AC代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl '
'
#define lson rt << 1
#define rson rt << 1 | 1
#define f(x, y, z) for (LL x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (LL i = (a); i <= (b); ++i)
using namespace std;
const int maxn = 5507;
const int maxm = 2e4 + 7;
const int mod = 998244353;
LL n, w, s;
LL a[maxn];
LL dp[maxn][maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
LL ans = -INF;
cin >> n >> w >> s;
_rep(i, 1, n) cin >> a[i];
_rep(i, 1, n)
{
_rep(j, 1, n) dp[i][j] = -INF;
}
dp[1][1] = a[1];
deque<LL> q;
_rep(i, 2, n)
{
q.clear();
for (LL j = w; j >= min(i - 1, w); j--)
{
while (!q.empty() && dp[i - 1][q.back()] <= dp[i - 1][j]) q.pop_back();
q.push_back(j);
}
for (LL j = min(i, w); j >= 1; j--)
{
while (!q.empty() && q.front() > j + s - 1) q.pop_front();
if (j > 1)
{
while (!q.empty() && dp[i - 1][q.back()] <= dp[i - 1][j - 1]) q.pop_back();
q.push_back(j - 1);
}
dp[i][j] = a[i] * j + dp[i - 1][q.front()];
}
}
_rep(i, 1, n)
{
ans = max(ans, dp[n][i]);
}
cout << ans << endl;
}
TLE代码:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl '
'
#define lson rt << 1
#define rson rt << 1 | 1
#define f(x, y, z) for (LL x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (LL i = (a); i <= (b); ++i)
using namespace std;
const int maxn = 5507;
const int maxm = 2e4 + 7;
const int mod = 998244353;
LL n, w, s;
LL a[maxn];
LL dp[maxn][maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
LL ans = -INF;
cin >> n >> w >> s;
_rep(i, 1, n) cin >> a[i];
_rep(i, 1, n)
{
_rep(j, 1, n) dp[i][j] = -INF;
}
dp[1][1] = a[1];
_rep(i, 2, n)
{
_rep(j, 1, min(i, w))
{
LL tmp = -INF;
_rep(k, max(1LL, j - 1), min(i - 1, min(w, j + s - 1)))
{
tmp = max(tmp, dp[i - 1][k]);
}
dp[i][j] = tmp + a[i] * j;
}
}
_rep(i, 1, n)
{
ans = max(ans, dp[n][i]);
}
cout << ans << endl;
}