题解 P5468 【[NOI2019]回家路线】

情非昔比 · 2019-07-16 20:01:39 · 题解

好水的一道NOI题

题目大意：

现在有n个城市，城市之间有m条火车可以到达。

第i条火车是从第x_i出发并到达y_i，是在p_i时间出发，并在q_i时间到达。

火车只能够在前一辆到达后才能乘坐。

设共乘坐了k辆火车，那么他的代价是(q_{s_{k}}+\left(A \times p_{s_{1}}^{2}+B \times p_{s_{1}}+C\right)+\sum_{j=1}^{k-1}\left(A\left(p_{s j+1}-q_{s_{j}}\right)^{2}+B\left(p_{s_{j+1}}-q_{s_{j}}\right)+C\right)

求最小代价。

解题思路：

一个DP题。

我们先将火车按照出发时间排序。

然后我们就可以进行DP了

我们用f_{i,j}表示时间j到达站点i的最小代价。

那我们有转移为f_{y_i,q_i}=min(f_{x_i,j}+calc(p_i,j))

其中calc(x)=Ax^2+Bx+C

然后转移即可。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
struct node{
    int x,y,p,q;
    bool operator<(node a)const{
        return p<a.p;
    }
}a[200100];
int n,m,A,B,C,T,ans;
int f[100100][1010];
int calc(int x){
    return x*x*A+x*B+C;
}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].p,&a[i].q);
        T=max(T,a[i].q);
    }
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)
        for(int j=0;j<=a[i].p;j++){
            if(f[a[i].x][j]==inf)continue;
            f[a[i].y][a[i].q]=min(f[a[i].y][a[i].q],f[a[i].x][j]+calc(a[i].p-j));
        }
    int ans=inf;
    for(int i=0;i<=T;i++)
        ans=min(ans,f[n][i]+i);
    printf("%d\n",ans); 
}