Ta nhận xét như sau:

• Nếu cố định hai đầu ~[l, r]~ thì mọi cách thu hoạch cây trong đoạn ~[l, r]~ đều có chi phí di chuyển không đổi là ~(r - l) \times C~.
• Do đó, ta tách cây được chọn ra như sau: Cây đầu sẽ có tiền bằng ~a[l] + l \times C~, cây cuối sẽ có tiền bằng ~a[r] - r \times C~. Các cây còn lại đều có chi phí ~a[i]~.

Từ đó, gọi ~f[i]~ là số tiền thu được cao nhất khi thu hoạch đến cây thứ ~i~, ta sẽ có các trường hợp:

• Nếu đây là cây đầu tiên: ~f[i] = a[i] + i \times C~.
• Nếu đây là cây khác cây đầu tiên: ~f[i] = f[i - 2] + a[i]~.
• Nếu không chọn cây này: ~f[i] = f[i - 1]~.

Sau đó ta sẽ lấy ~\max(f[i] - i \times C)~ nghĩa là chi phí chọn cây cuối cùng.

Độ phức tạp: ~O(n)~.

Code tham khảo:

void solve() {
    int n, C;
    cin >> n >> C;
    vector<int> a(n + 5);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<long long> f(n + 5, 0);
    long long ans = a[1];
    for(int i = 1; i <= n; i++) {
        f[i] = max(f[i - 1], a[i] + 1LL * i * C);
        if (i >= 2) f[i] = max(f[i], f[i - 2] + a[i]);
        ans = max(ans, f[i] - 1LL * i * C);
    }
    cout << ans;
}