题目内容

P1359

大意:长江上有 n 个游艇出租站,从 ij 需要 r(i,j) 元,求 1n 的最少花费

解题思路

可以建模成图论的题来做 Dij 或者 Floyd,但没有必要,因为这就是一个 DAG,直接每个节点上更新就可以了,我们设 f_i 为从 1 到 i 的最小花费,则枚举 [1,i) 的每一个点,看能不能找到更小的就可以了。方程式:

f_i=\min_{j\in[1,i)}\lbrace f_j+r(j,i)\rbrace

记得一开始要赋很大的初始值,然后从边界开始:f_1=0,因为没有任何花费

#include <cstdio>

const int maxn=205;
int n,f[maxn],a[maxn][maxn];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        f[i]=0x3f3f3f3f;
        for(int j=i+1;j<=n;j++)
            scanf("%d",&a[i][j]);
    }
    f[n]=0x3f3f3f3f;
    f[1]=0;
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
            f[i]=min(f[i],f[j]+a[j][i]);
    printf("%d\n",f[n]);
    return 0;
}
最后修改日期:2020年3月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。