首页 > 其他分享 >题解:P7082 [NWRRC2013] Dwarf Tower

题解:P7082 [NWRRC2013] Dwarf Tower

时间:2024-11-06 15:11:05浏览次数:2  
标签:Dwarf int 题解 IOS P7082 Tower dp

涉及知识点:动态规划。

解题思路

设 \(dp_i\) 为得到 \(i\) 最小的花费。

可以得到转移方程:\(dp_{a_i} = \min(dp_{x_i} + dp_{y_i}, dp_{a_i})\)。

很明显最多迭代 \(n\) 次,还需要再外面套一个循化即可。

但是有些 OJ 没有洛谷跑得快,所以需要加一点优化。

如果当前循环没有更新任何一个数,说明当前每个数都是最优的,直接退出循环。

代码

#include <bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fre(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);

const int N = 100010;

int n, m;
int a[N], x[N], y[N], z[N];
int dp[N];

signed main() {
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        x[i] = a;
        y[i] = b;
        z[i] = c;
    }
    for (int i = 1; i <= n; i ++ ) dp[i] = a[i];
    for (int i = 1; i < n; i ++ ) {
        bool flag = false;
        for (int j = 1; j <= m; j ++ ) {
            if (dp[y[j]] + dp[z[j]] < dp[x[j]]) {
                dp[x[j]] = dp[y[j]] + dp[z[j]];
                flag = true;
            }
        }
        if (!flag) break;
    }
    cout << dp[1] << endl;
    return 0;
}

标签:Dwarf,int,题解,IOS,P7082,Tower,dp
From: https://www.cnblogs.com/zla2012/p/18530244

相关文章

  • 【题解】CF1956
    CF1956A简要题意有\(n\)个人玩一个游戏,把这\(n\)个人分别编号为\(1\)到\(n\)。每一轮,编号为\(a_1,a_2,\ldots,a_k\)(\(a\)序列递增)的人会被踢出这个游戏,剩下的人会补齐空位并重新从\(1\)开始编号。当某一轮没有人被踢出时,游戏结束,剩下没有被踢出的人成为......
  • “SSL 证书验证失败”问题解决方法“urllib.error.URLError: <urlopen error [SSL: CER
    第一部分:问题描述第二部分:解决方法错误的代码:dataset_train=datasets.MNIST('../data/mnist/',train=True,download=True,transform=trans_mnist)dataset_test=datasets.MNIST('../data/mnist/',train=False,download=True,transform=trans......
  • P6667 [清华集训2016] 如何优雅地求和 题解
    一道非常有启发性的题目。思路考虑对于一个给出点值的多项式函数如何处理。我们发现,对于一个\(m\)次多项式\(f(x)\),由于\(\binom{x}{i}\)为\(i\)次多项式,所以说我们必定可以把一个多项式函数写成如下模样:\[F(k)=\sum_{i=0}^m\binom{k}{i}f_i\]可以看出,\(f_i\)实际上......
  • CSP-J2024题解
    T1扑克牌本题要求:在给定的扑克牌的基础上,还需要多少张牌可以让扑克牌凑成一整套,试题中读入的字符串每个都代表一张合法的扑克牌。可以使用C++STL中的set(集合)完成本题。这是因为,set可以自动去重,去除重复的牌(字符串)后,剩下的字符串就是实际拥有的不同的牌。而一副扑克牌有......
  • ABC378 E 题解
    ABC378E题解题意给定序列\(A\),求\(\sum_{1\lel\ler\len}(\sum_{l\lei\ler}A_i\modM)\)计算所有区间和取模之后的结果再求和。注意外层是没有取模的。如果是外层也要取模的情况,那还是十分好办的,直接贡献法计算每个数字被统计了多少次就可以了。问题就在于外层没......
  • 2024强网杯web题解
    PyBlocklyfromflaskimportFlask,request,jsonifyimportreimportunidecodeimportstringimportastimportsysimportosimportsubprocessimportimportlib.utilimportjsonapp=Flask(__name__)app.config['JSON_AS_ASCII']=Falseblacklis......
  • 2024newstarweb题解
    w1headach3会赢吗源码flag碎片X1:ZmxhZ3tXQTB3再次查看源码flag碎片X2:IV95NF9yM2Fs第三个页面也是直接查看源码直接改源码flag碎片X3:MXlfR3I0c1B下一个页面直接禁用jsflag碎片X4:fSkpKcyF9ZmxhZ3tXQTB3IV95NF9yM2FsMXlfR3I0c1BfSkpKcyF9base64解码即......
  • WPF程序弹出页中按钮在触摸屏(电容屏)上点击事件需要点十次才能触发的问题解决方法
    一、事件背景介绍1.功能简述:主页面是一个DataGrid列表,点击DataGrid行,弹出子页面;子页面根据数据加载多个Button按钮,如下图,就是这个页面中的按钮,在触摸屏上触摸点击,需要点击十次才能成功,使用鼠标点击一下就能成功。 主要代码如下://WPF前端<DataGridx:Name="scanDtl......
  • P11236 「KTSC 2024 R1」水果游戏 题解
    很有意思的一道题。思路首先将相邻一样的数合并,每个元素变成一个二元组,表示数与出现次数。考虑什么时候不能合并。我们发现假如充分合并后,现在有连续的三个数\(x_1,x_2,x_3\),以及他们各自的出现次数\(y_1,y_2,y_3\)。如果\(x_1>x_2,x_3>x_2\)。我们想要合并这三个,必须要......
  • xss-labs题解
    xss—labsxss—labslevel1(GET型)level2(闭合)level3(htmlspecialchars绕过)level4(左右尖括号过滤)level5(a标签法)level6(大小写绕过)level7(双写绕过)level8(利用href自动Unicode解码特性)level9(注释绕过后端判断)xss—labs题目链接BUUCTF在线评测题目源码xss-lab/lev......