PAT.1033 To Fill or Not to Fill

题目链接
说实话一上来看到题目就觉得是动态规划，然后就写了，写完发现并过不了，在局部最优解上欠考虑。
于是转向贪心，只要梳理清楚根本的思路这道题还是很简单的：寻找满油范围内可达的比当前油价低的站点，如果有就加刚好够用的油量前往，如果没有就尽可能寻找可达范围内价格较低的站，并在当前站把油加满。

那么dp行不行呢？我一开始将状态dp[i]设计为恰好到达第i个站点时花费的最少油钱，但这样写是不行的，因为在当前站点油价为续航范围内最低时要加满，而不能只加足够开到下一个局部油价最低点。

#include

using namespace std;
typedef long long ll;

int tankSize,stationCnt;
double price,dis,disPerUnit,maxReachableDis,disFromStart,fullDis,dp[505];
vector > stations;

int main(){
    for(int i = 0 ; i < 505 ; ++i) dp[i] = INT_MAX;
    cin>>tankSize>>dis>>disPerUnit>>stationCnt;
    fullDis = tankSize * disPerUnit;
    for(int i = 0 ; i < stationCnt ; ++i){
        cin>>price>>disFromStart;
        stations.push_back({price,disFromStart});
    }
    stations.push_back({0,dis});
    sort(stations.begin(),stations.end(),[](const pair a,const pair b){
        return a.second < b.second;
    });
    for(int i = 0 ; i < stationCnt + 1; ++i){
        double currentDisFromStart = stations[i].second;
        if(currentDisFromStart > maxReachableDis){
            printf("The maximum travel distance = %.2f",maxReachableDis);
            return 0;
        }
        if(currentDisFromStart == 0) dp[i] = 0;
        maxReachableDis = currentDisFromStart + fullDis; 
        for(int j = 0 ; j < i ; ++j){
            if(stations[j].second + fullDis < currentDisFromStart) continue;
            double disDiff = currentDisFromStart - stations[j].second;
            dp[i] = min(dp[i],dp[j] + disDiff / disPerUnit * stations[j].first);
        }
    }
    printf("%.2f",dp[stationCnt]);
}

寻找满油巡航范围内比当前站油价低的站点，如果存在就加恰好前往该站需要的油量，如果不存在就在当前站加满。
特别注意两点：

即使在当前站加满油也没有可到达的站的情况出发点没有加油站的情况

#include

using namespace std;
typedef long long ll;

int stationCnt,currentStation;
double price,dis,disPerUnit,maxReachableDis,disFromStart,fullDis,minCost,tankSize,currentTank;
vector > stations;

int main(){
    cin>>tankSize>>dis>>disPerUnit>>stationCnt;
    fullDis = tankSize * disPerUnit;
    for(int i = 0 ; i < stationCnt ; ++i){
        cin>>price>>disFromStart;
        stations.push_back({price,disFromStart});
    }
    stations.push_back({0,dis});
    sort(stations.begin(),stations.end(),[](const pair a,const pair b){
        return a.second < b.second;
    });
    if(stations[0].second > 0){		//起始点无站
        printf("The maximum travel distance = 0.00");
        return 0;
    }
    while(currentStation != stationCnt){
        double currentPrice = stations[currentStation].first;
        double currentDisFromStart = stations[currentStation].second;
        int reachableMinPriceStation = currentStation + 1;
        if(currentDisFromStart + fullDis < stations[currentStation + 1].second){		//满油范围内没有站
            printf("The maximum travel distance = %.2f",currentDisFromStart + fullDis);
            return 0;
        }
        for(int j = currentStation + 1 ; j <= stationCnt && currentDisFromStart + fullDis >= stations[j].second ; ++j){
            //寻找满油范围内是否存在更便宜的油站(比当前油站便宜就立刻移动,没有就加满并移动到局部最便宜)
            if(stations[j].first < currentPrice){		//比当前油站便宜立刻移动,加刚好开到下一站的油量
                double needUnit = (stations[j].second - currentDisFromStart) / disPerUnit;
                if(needUnit > currentTank){		//需要在当前站额外加油
                    minCost += (needUnit - currentTank) * currentPrice;
                    currentTank = 0;
                }else currentTank -= needUnit;
                currentStation = j;
                reachableMinPriceStation = -1;
                break;
            }
            if(stations[j].first < stations[reachableMinPriceStation].first) reachableMinPriceStation = j;
        }
        if(reachableMinPriceStation != -1){		//前往局部最低油价站，并在当前站加满
            minCost += (tankSize - currentTank) * currentPrice;
            currentTank = tankSize - (stations[reachableMinPriceStation].second - currentDisFromStart) / disPerUnit;
            currentStation = reachableMinPriceStation;
        }
    }
    printf("%.2f",minCost);
}