計蒜客資訊學7月普及組模拟賽 - C 收獲（逆向DP）

​​計蒜客資訊學7月普及組模拟賽 - C 收獲​​

題目

有 n 個地點，每個點有可能是果樹或者亭子。初始有一個興奮度 w，經過果樹可以選擇“收獲” 一次，收獲值為目前興奮度

，但是興奮度會下降

；經過亭子可以選擇花費

的收獲值，但是興奮度會上升

。問從 1 走到 n，能獲得最大收獲值？

分析

好題

看起來跟背包問題很像，每次選擇操作或者不操作，問最後最值。

首先經過一個地點選擇收獲或者不收獲，是會改變目前興奮值的，而興奮值的改變還會影響後面的收獲值，也就是目前操作會影響後面所有的操作，因為收獲花費都跟 w 有關。也就是有後效性，正着DP肯定不行。

倒過來看，将

表示為從第

思維：将每次興奮值的改變看作後面的所有收獲的改變，也就是目前興奮值改變後，可以看作不變，變的是後面的所有操作：

。兩個等效的。

即：興奮值一直保持在 w 的水準。

狀态轉移方程：

1. 對于經過果樹：

   不收獲的話，就是

2. ，收獲的話，就是看作後面所有操作都降低
3. ，而目前興奮值還是不變，為 w ，最後加上目前收獲的
4. 。

5. 經過亭子：

   道理是一樣的：

前面初始化就是找到從後面數第一個果樹，将他的值

作為

數組初始值。

因為亭子後面如果沒有果樹就沒有意義，（反正後面也不會有收獲）。

代碼

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
#define max(a,b) a>b?a:b
typedef long long ll;

double n, k, c, w;
double a[N], id[N], dp[N];

int main()
{
    scanf("%lf%lf%lf%lf", &n, &k, &c, &w);
    for (int i = 1; i <= n; i++){
        scanf("%lf%lf", &id[i], &a[i]);
    }
    int t = n;
    while(id[t--] == 2) {}
    dp[t + 1] = a[t + 1] * w;
    for (int i = t; i >= 1; i--){
        if(id[i] == 1){                     // 果樹
            dp[i] = max(dp[i + 1], dp[i + 1] * (1.0 - k * 0.01) + a[i] * w);
        }else{                              // 亭子
            dp[i] = max(dp[i + 1], dp[i + 1] * (1.0 + c * 0.01) - a[i] * w);
        }
    }
    printf("%.2lf\n", dp[1]);
    return 0;
}