FZYZOJ 1917(DP+单调队列)

FJYZOJ 1917
这题的思路相似,设$dp(i)$为$[i,n]$必选$i$的最优解,则
$$dp(i)=max(dp(j)) \times k + v_i$$
$max(dp(j))$是$[i,i+m]$中的最大值,这样做是$O(n^2)$的。
一段的最大值,显然用单调队列来优化,这样复杂度降到了$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, m, vi[MAXN], q[MAXN], l, r;
db k, dp[MAXN];
void clean() {
ms(dp, 0), ms(q, 0);
l = 1, r = 0, dp[n + 1] = 0.0;
}
void solve() {
clean();
for (int i=1;i<=n;i++) scanf("%d", &vi[i]);
for (int i=n;i>=1;i--) {
while (l <= r && q[l] > i + m) l++;
while (l <= r && dp[q[r]] <= dp[i + 1]) r--;
q[++r] = i + 1;
dp[i] = (dp[q[l]]) * k + vi[i];
}
db ans = 0.0;
for (int i=1;i<=m;i++) ans = max(ans, dp[i]);
printf("%.2f\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
#endif
scanf("%d%d%lf", &n, &m, &k), solve();
fclose(stdin); fclose(stdout);
return 0;
}

题目描述

π+e 去遗迹探险,遗迹里有 N 个宝箱,有的装满了珠宝,有的装着废品。

π+e 手上有 n+e 的地图,所以他知道每一个宝箱的价值,但是他不喜欢走回头路,所以要按顺序拿这 N 个宝箱中的若干个。

但是拿宝箱很累的。一开始 π+e 的体力是 1,每得到一个宝箱之后, π+e 得到的价值是体力 × 宝箱的价值,之后他的体力就会变为原来的 k 倍 (0<k<1)。

π+e 不喜欢连续放过很多宝箱,所以任意一段长度为 M 的序列中,π+e一定要取走其中的一个宝箱。

现在 π+e 想知道他能得到的最大价值和。

输入格式

第一行,两个整数 N, M ,表示的含义如题目中所述;

第二行,一个小数 k,表示的含义如题目中所述,最多 4 位小数;

第三行,N 个整数,第 i 个整数表示第 i 个宝箱的价值。

输出格式

输出一行,一个实数,表示 π+e 能得到的最大价值和,四舍五入保留两位小数。

输入样例

3 2
0.1
1 2 3
输出样例

2.30
数据规模与约定

【样例解释】 取第 2 个和第 3 个宝箱,则价值和为 2×1 + 3×0.1 = 2.3

【数据规模与约定】

对于 30% 的数据,有 1 ≤ N ≤ 10;

对于 60% 的数据,有 1 ≤ N ≤ 1000;

对于 100% 的数据,有 1 ≤ N ≤ 100000,1 ≤ M ≤ N ,0 < k < 1,−10^9 ≤ 所有宝箱的价值 ≤ 10^9 。

建议在程序运行过程中使用 double 类型存储数据

------ 本文结束 ------