有状态转移+有限容量=>01背包

#include <algorithm>
#include <iostream>
#include <vector>
#define Max 1e18
using namespace std;

int solution(int distance, int n, std::vector<std::vector<int>> gas_stations) {
    sort(gas_stations.begin(), gas_stations.end());
    gas_stations.insert(gas_stations.begin(), { 0, 0 });
    gas_stations.push_back({ distance, 0 });
    n++;
    vector<vector<long long>> dp(n + 1, vector<long long>(405, Max));
    dp[0][200] = 0; 

    for (int i = 1; i <= n; i++) {
        int dist = gas_stations[i][0] - gas_stations[i - 1][0]; 
        if (dist > 400) {
            return -1;
        }
        for (int j = 0; j <= 400; j++) {
            if (i == n) {
                if(j+dist<=400)dp[i][200] = min(dp[i][200], dp[i - 1][200 + dist]);
                continue;
            }
            for (int k = 0; k <= j; k++) { 
                if (j - k + dist <= 400) { 
                    dp[i][j] = min(dp[i][j], dp[i - 1][j + dist - k] + k * gas_stations[i][1]);
                }
                if (j + dist <= 400) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j + dist]);
                }
            }
        }
    }
    //for(int i=0;i<=400;i++)cout<<i<<" "<< dp[n][i] << endl;
    //cout<< (dp[n][200] == Max ? -1 : dp[n][200])<<endl;
    return dp[n][200] == Max ? -1 : dp[n][200];
}

int main() {
  std::vector<std::vector<int>> gasStations1 = {
      {100, 1}, {200, 30}, {400, 40}, {300, 20}};
  std::vector<std::vector<int>> gasStations2 = {
      {100, 999},  {150, 888},  {200, 777}, {300, 999},
      {400, 1009}, {450, 1019}, {500, 1399}};
  std::vector<std::vector<int>> gasStations3 = {{101}, {100, 100}, {102, 1}};
  std::vector<std::vector<int>> gasStations4 = {
      {34, 1},     {105, 9},  {9, 10},    {134, 66}, {215, 90},
      {999, 1999}, {49, 0},   {10, 1999}, {200, 2},  {300, 500},
      {12, 34},    {1, 23},   {46, 20},   {80, 12},  {1, 1999},
      {90, 33},    {101, 23}, {34, 88},   {103, 0},  {1, 1}};

  std::cout << (solution(500, 4, gasStations1) == 4300) << std::endl;
  std::cout << (solution(500, 7, gasStations2) == 410700) << std::endl;
  std::cout << (solution(500, 3, gasStations3) == -1) << std::endl;
  std::cout << (solution(100, 20, gasStations4) == 0) << std::endl;
  std::cout << (solution(100, 0, std::vector<std::vector<int>>{}) == -1)
            << std::endl;

  return 0;
}