NOI2019 回家路线 DP「NOI2019」回家路线

「NOI2019」回家路线

链接

loj

思路

f[i][j]第i个点，时间为j，暴力转移
复杂度O(m*t),好像正解是斜率优化，出题人太不小心了233

代码

复制代码#include <bits/stdc++.h> using namespace std; const int N=2e5+7,INF=0x3f3f3f3f; int n,m,A,B,C,f[100007][1007]; struct node {int x,y,p,q;}a[N]; int fff(int x) {return A*x*x+B*x+C;} bool cmp(node a,node b) {return a.p<b.p;} vector<int> G[N]; int read() { int x=0,f=1; char s=getchar(); for(;s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0'; return x*f; } int main() { freopen("route.in","r",stdin),freopen("route.out","w",stdout); n=read(),m=read(),A=read(),B=read(),C=read(); int Maxtime=0; for(int i=1;i<=m;++i) { a[i].x=read(),a[i].y=read(),a[i].p=read(),a[i].q=read(); Maxtime=max(Maxtime,a[i].q); } sort(a+1,a+1+m,cmp); memset(f,0x3f,sizeof(f)); f[1][0]=0; for(int i=1;i<=m;++i) for(int j=0;j<=a[i].p;++j) f[a[i].y][a[i].q]=min(f[a[i].y][a[i].q],f[a[i].x][j]+fff(a[i].p-j)); int ans=INF; for(int j=0;j<=Maxtime;++j) ans=min(ans,f[n][j]+j); printf("%dn",ans); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7,INF=0x3f3f3f3f;
int n,m,A,B,C,f[100007][1007];
struct node {int x,y,p,q;}a[N];
int fff(int x) {return A*x*x+B*x+C;}
bool cmp(node a,node b) {return a.p<b.p;}
vector<int> G[N];
int read() {
    int x=0,f=1; char s=getchar();
    for(;s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0';
    return x*f;
}
int main() {
    freopen("route.in","r",stdin),freopen("route.out","w",stdout);
    n=read(),m=read(),A=read(),B=read(),C=read();
    int Maxtime=0;
    for(int i=1;i<=m;++i) {
        a[i].x=read(),a[i].y=read(),a[i].p=read(),a[i].q=read();
        Maxtime=max(Maxtime,a[i].q);
    }
    sort(a+1,a+1+m,cmp);
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<=m;++i)
        for(int j=0;j<=a[i].p;++j)
            f[a[i].y][a[i].q]=min(f[a[i].y][a[i].q],f[a[i].x][j]+fff(a[i].p-j));
    int ans=INF;
    for(int j=0;j<=Maxtime;++j) ans=min(ans,f[n][j]+j);
    printf("%dn",ans);
    return 0;
}