洛谷4438 [HNOI/AHOI2018]道路

Luogu

算法

首先你要把题目看懂。

设 $dp_{u,i,j}$ 表示节点 $u$ 向上有 $i$ 条未翻修的公路、$j$ 条未翻修的铁路的最小不便利值。

转移时,考虑该节点修公路还是修铁路:

$$ dp_{u,i,j}=\min\begin{cases}dp_{s_u,i,j}+dp_{t_u,i,j+1}\\dp_{s_u,i+1,j}+dp_{t_u,i,j}\end{cases} $$

边界是当 $u$ 是乡村时,$dp_{u,i,j}=c_u(a_u+i)(b_u+j)$。

然而这样子写得不好可能会 MLE,需要注意一下...

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20000+10;

int n;
int ch[N][2];
int a[N<<1],b[N<<1],c[N<<1];
ll dp[N][45][45];

inline ll f(int u,int x,int y) {
    if (u>=n) return 1ll*c[u]*(a[u]+x)*(b[u]+y);
    else return dp[u][x][y];
}
inline void dfs(int u,int x,int y) {
    if (u>=n) return;
    dfs(ch[u][0],x+1,y),dfs(ch[u][1],x,y+1);
    for (re int i=0;i<=x;++i)
        for (re int j=0;j<=y;++j)
            dp[u][i][j]=min(
                f(ch[u][0],i+1,j)+f(ch[u][1],i,j),
                f(ch[u][0],i,j)+f(ch[u][1],i,j+1)
            );
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        ch[i][0]=read(); if (ch[i][0]<0) ch[i][0]=-ch[i][0]+n-1;
        ch[i][1]=read(); if (ch[i][1]<0) ch[i][1]=-ch[i][1]+n-1;
    }
    for (re int i=n;i<=n+n-1;++i) a[i]=read(),b[i]=read(),c[i]=read();
    dfs(1,0,0); printf("%lld\n",dp[1][0][0]);
    return 0;
}
最后修改:2019 年 10 月 21 日 05 : 30 PM

3 条评论

  1. smy

    手动@wfj_2048

    1. M_sea
      @smy

发表评论