Consegne liguri

Chiarimenti
1

Il codice che allego sotto risolve solo i casi di esempio e quelli del subtask 4

#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <climits>
using namespace std;
vector<int>succ,scende;
vector<long long >costi;
int n, k;
int a;
int da;
vector<long long> prefs;
vector<int>best;
long long memo[200001];
int decr = 1;

long long DP1(int da, int a) {
    int i, j;
    memo[a] = 0;
    long long c; // = LLONG_MAX;
    if (a == da + 1) {
        return costi[da];
    }
    memo[a - 1] = costi[a - 1];
    for (i = a - 2; i >= da; i--) {
        if (costi[i] >= costi[i + 1]) {
            memo[i] = memo[i + 1] + costi[i];
        }
        else {
            c = LLONG_MAX;
            for (j = 1; j <= k; j++) {
                if (j + i > a)
                    break;
                c = min(c, memo[i + j] + j * costi[i]);
            }
            memo[i] = c;
        }
    }
    return memo[da];
}

void pianifica (int N, int K, vector<int> C) {
    n = N;
    k = K;
    costi.resize(n);
    for (int i = 0; i < N; i++) {
        costi[i] = C[i];
        if (i > 0) {
            if (costi[i] > costi[i - 1])
                decr = 0;
        }
    }
    //succ.resize(N);
    //decr = 0;
    if (decr) {
        prefs.resize(n);
        prefs[0] = costi[0];
        for (int i = 1; i < n; i++)
            prefs[i] = costi[i] + prefs[i - 1];
    }
   
}

long long viaggia (int l, int r) {
    if (decr) {
        if (l > 0)
            return prefs[r - 1] - prefs[l - 1];
        else
            return prefs[r - 1];
    }   
    return DP1(l, r);
}

// GRADER DI ESEMPIO, NON MODIFICARE

#ifndef EVAL
int main () {
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;

    vector<int> C(N);
    for (int &c: C) cin >> c;
    pianifica(N, K, C);
    
    int Q; cin >> Q;

    for (int i = 0; i < Q; i++) {
        int l, r; 
        cin >> l >> r;
        cout << viaggia(l, r) << endl;
    }
}
#endif

Potreste propormi un caso (fra i tanti) in cui sbaglia.
Grazie in anticipo.
P.S.
E’ possibile anche tornare indietro da l per arrivare ad una città che precede l dove la benzina costa meno?
Ad esempio con:
6 6
1 100 200 200 400 500
2
0 6
1 6
le soluzioni giuste sono 6 e 500 o 6 e 106 ?

2

Salve, utilizzando questo caso di input

3 2
5 8 10
1
0 3

Il tuo codice stampa 20 invece di 18.
Riguardo al P.S. Non è possibile muoversi verso sinistra. Nel testo effettivamente non è ben specificato però lo si può intuire dal fatto che il consumo di benzina sia specificato solamente per quando ci sia muove dalla città i alla città i + 1 (“Per andare dalla città 𝑖 alla città 𝑖 + 1, Luca consuma esattamente un litro di benzina”)

3

Grazie per la risposta, partendo dalla città 0 come fa a non pagare almeno 5UFV?
Il mio codice opera nel seguente modo:
con k=2 i percorsi possibili sono:

  1. 0,1,2,3 costo 5+8+10=23
  2. 0,1,3 costo 5+2*8=21
  3. 0,2,3 costo 5*2+10=20 ??
    ed il costo minimo è 20.

D’accordo con te per il P.S.
Vuoi dire che fa il percorso 3) e mentre passa dalla città 1 può fare un litro lì pagando 8 e non gli serve far benzina quando arriva alla città 2: quindi 5*2+8=18?
Tante grazie rivedrò il codice.

4

Sì esatto, per spendere 18UFV vengono fatti i seguenti passaggi

  • Nella città 0 prende 2 litri di benzina per un totale di 10UFV.
  • Mi muovo alla città 1 utilizzando un litro di benzina, lasciando un litro nel serbatoio
  • Nella città 1 compro un litro di benzina al costo di 8UFV per un totale di 18UFV
  • Mi muovo alla città 2, lasciando un litro di benzina nel serbatoio
  • Mi muovo alla città 3 utilizzando l’ultimo litro di benzina