NOI2019|NOI2019 回家路线 DP
「NOI2019」回家路线
链接 【NOI2019|NOI2019 回家路线 DP】loj
思路 f[i][j]第i个点，时间为j，暴力转移
复杂度O(m*t),好像正解是斜率优化，出题人太不小心了233
代码
#include
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 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("%d\n",ans);
return 0;
} 推荐阅读
- 粪娃嫫
- 排球比赛
- 望京琐记1
- 走好每一步
- 还记风吹水上鳞
- 2018、5、27，星期天，晴（4#）
- 休班了就回家
- 这周你回家么（）
- 我不想独自长大—等你回家时，我已长大成人
- 想要吃的健康，从回家做饭开始