P1917 -- 探险
时间限制：1000MS 内存限制：131072KB
题目描述(explore.cpp)
π+e去遗迹探险,遗迹里有 N 个宝箱,有的装满了珠宝,有的装着废品。
π+e手上有 n+e的地图,所以他知道每一个宝箱的价值,但是他不喜欢走回头路,所以要按顺序拿这 N 个宝箱中的若干个。
但是拿宝箱很累的。一开始 π+e的体力是 1, 每得到一个宝箱之后, π+e得到的价值是体力 × 宝箱的价值,之后他的体力就会变为原来的 k倍 (0<k<1)。
π+e 不喜欢连续放过很多宝箱,所以任意一段长度为 M 的序列中, π+e 一定要取走其中的一个宝箱。
现在 π+e 想知道他能得到的最大价值和。
输入格式(explore.in)
第一行,两个整数 N,M,表示的含义如题目中所述;
第二行,一个小数 k,表示的含义如题目中所述,最多 4 位小数;
第三行,N 个整数,第 i 个整数表示第 i个宝箱的价值。
输出格式(explore.out)
输出一行,一个实数,表示 π+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 类型存储数据
題好像並沒有多難，但是看到以後沒有什麼思路，還是做題太少，抄題解太多，
在某次取完后所有後面的結果都會乘上k，而且和後面取多少個無關，所以逆推，每次取的時候給它乘一個k再加上a[i]，
f[i]=max(f[j]*k+a[i]) (i<j<=i+m)
用單調隊列維護一個區間最大值即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,m,a[maxn];
int q[maxn],head=,tail=;
double k,f[maxn]; int main()
{
scanf("%d%d%lf",&n,&m,&k);
for(int i=;i<=n;i++)scanf("%d",&a[i]); for(int i=n;i>=;i--){
while(head<=tail && q[head]>m+i)head++;
while(head<=tail && f[q[tail]]<f[i+])tail--;
q[++tail]=i+;
f[i]=f[q[head]]*k+a[i];
}
double ans=-0x7fffffff;
for(int i=;i<=m;i++)ans=max(ans,f[i]);
printf("%.2lf\n",ans);
}