这道题是当初考过的模拟题,当时理解得迷迷糊糊的,以至于今天又打一遍
按照常规的思路,从前往后推,每个星球选或不选
但仔细分析,发现这样是有后效性的
为什么呢?我们可以来推一推这个过程
初始为$w$,开采一次后(修复同理)变成$w*(1-k\%)$,假设又开采,金钱+$w*(1-k\%)*a_i$
把后面括起来,即+$w*((1-k\%)*a_i)$
看懂了吗?也就是说每开采一次,相当于后面每个$a_i$都缩小了$k\%$,即后面的问题规模缩小了$k\%$,后面的决策受到了前面的影响
所以我们从后往前推,令$f[i]$表示$i o n$的最大收入,且$i$的规模为$1$
那么有
$$f[i] = left{egin{matrix}
max(f[i+1],a[i]+f[i+1]*(1-k\%)),type = 1\
max(f[i+1],-a[i]+f[i+1]*(1+c\%)),type = 2
end{matrix}
ight.$$
最后再$*w$即可(我们算的是问题规模为$1$的$f[1]$)
代码如下
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <vector> 6 #define ll long long 7 using namespace std; 8 9 template <typename T> void in(T &x) { 10 x = 0; T f = 1; char ch = getchar(); 11 while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} 12 while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();} 13 x *= f; 14 } 15 16 template <typename T> void out(T x) { 17 if(x < 0) x = -x , putchar('-'); 18 if(x > 9) out(x/10); 19 putchar(x%10 + 48); 20 } 21 //------------------------------------------------------------- 22 23 const int N = 1e5+7; 24 int n,k,c,w,a[N],t[N]; 25 double f[N]; 26 27 int main() { 28 int i; in(n); in(k); in(c); in(w); 29 for(i = 1;i <= n; ++i) in(t[i]),in(a[i]); 30 f[n] = t[n] == 1 ? a[n]:0; 31 for(i = n-1;i >= 1; --i) { 32 if(t[i] == 1) f[i] = max(f[i+1],a[i]+f[i+1]*(1-k*0.01)); 33 else f[i] = max(f[i+1],-a[i]+f[i+1]*(1+c*0.01)); 34 } 35 printf("%.2lf",f[1]*w); 36 return 0; 37 }