题解 P2317 【[HNOI2005]星际贸易】

· · 题解

拿到这道题蒟蒻的头脑非常混乱……

再仔细想想，发现这道题可以分成两部分解决，第一部分是选择哪些星球进行销售。第二部分是在第一部分的基础上进行的，计算此时所需要花费的最小代价。

第一部分其实非常简单的啦，就是一个背包dp，dp[i][j]=max(dp[i-1][j-a[i]]+b[i],dp[i-1][j])，其中只有dp[0][0]=0，其它全部为负无穷大。

接下来进行dp的路径还原就可以得到第一部分选择了哪些星球了。（刚开始没有好好看题，这样的选择竟然是唯一的，我傻爆了）。暂且称这一部分选出的星球为必选星球。

第二部分的dp也很好想了。设f[i][j]表示前i个星球经过之后停靠在第i个星球并且加过反物质材料、维护过之后所需要的最小代价。其实题目中这个R<=1E9的条件并没有什么卵用……可以发现，最多携带2n的燃料就可以完成旅行了。

然后就开始花式dp……

f[i][j]=min(f[k][l]+(j-l+2)*P[i]+F[i])，其中k满足：最近必选星球的位置<=k<j且L[j]-L[k]<=L，且2<=l<=j+2.

这样dp是O(n^4)的，而且常数较大，我们需要改进啊。。

容易发现，上面的dp可以转换成：f[i][j]=min(f[k][j+2]+F[i],f[i][j-1]+P[i])，其中k的取值范围不变。

但是这样的复杂度为O(n^3)，还是不够。我们会发现这个递推式还可以使用单调队列进行优化。最后的复杂度为O(n^2)。

f[0][R]=0，其它为正无穷大。

···cpp

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <functional>
#include <time.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2005, maxf = 4005;
int dp[maxn][maxn], f[maxn][maxf], sell[maxn], money[maxn], dist[maxn], price[maxn], fix[maxn];
int que[maxf][maxn], he[maxf], ta[maxf];
bool chosen[maxn];
int main(){
    int n, m, maxF, maxD;
    scanf("%d%d%d%d", &n, &m, &maxF, &maxD);
    if(maxF > 2 * n) maxF = 2 * n;
    for(int i = 1; i <= n; i++) scanf("%d%d%d%d%d", sell+i, money+i, dist+i, price+i, fix+i);
    for(int i = 1; i <= n; i++) if(dist[i] - dist[i - 1] > maxD){
        puts("Poor Coke!");
        return 0;
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++){
        if(dp[i - 1][j] >= 0) dp[i][j] = dp[i - 1][j];
        if(j >= sell[i] && dp[i - 1][j - sell[i]] >= 0)
            dp[i][j] = max(dp[i][j], dp[i - 1][j - sell[i]] + money[i]);
    }
    int maxS = 0;
    for(int i = 0; i <= m; i++) if(dp[n][i] > dp[n][maxS]) maxS = i;
    for(int i = n, j = maxS; i >= 1; i--){
        if(dp[i][j] == dp[i - 1][j]) continue;
        else chosen[i] = true, j -= sell[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][maxF] = 0;
    que[maxF][ta[maxF]++] = 0;
    for(int i = 1; i <= n; i++)
    for(int j = 0; j <= maxF; j++){
        if(price[i] > 0 && j > 0) f[i][j] = min(f[i][j], f[i][j - 1] + price[i]);
        if(ta[j + 2] > he[j + 2]) f[i][j] = min(f[i][j], f[que[j + 2][he[j + 2]]][j + 2] + fix[i]);
        if(chosen[i]) he[j] = ta[j] = 0;
        while(ta[j] > he[j] && f[que[j][ta[j] - 1]][j] >= f[i][j]) ta[j]--;
        que[j][ta[j]++] = i;
        while(he[j] < ta[j] && dist[i + 1] - dist[que[j][he[j]]] > maxD) he[j]++;
    }
    int minC = 0;
    for(int i = 0; i <= maxF; i++) if(f[n][i] < f[n][minC]) minC = i;
    if(f[n][minC] == INF) puts("Poor Coke!");
    else printf("%d %d", dp[n][maxS], dp[n][maxS] - f[n][minC]);
    return 0;
}
···