首页 > 代码库 > 红字差评系列2.dwarf
红字差评系列2.dwarf
【题目分析】
首先按照题目给出的样例想到只要每个物品的价格都用能够合成他的两个物品来更新，一边读入一边更新就好了，后来又发现如果出现这样的情况：1 2 3在2 5 6 的前面，那我们就需要先更新2在更新1.对吧就这样我就用了dfs然后完美爆栈75分，当然在这之前我还考虑到了如果一个物品可以被多个物品更新的话，那我们就是用边表记录下来，找每一组，但并没有实现（边表的孩子也是75hh），南城甚至建了棵树。但AC的同学是这么做（作）的，读入的时候更新一遍，读完了再倒回来更新一遍....为什么！！！（数据水）
#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define ll long longconst int maxn=20010;int n,m;ll c[maxn];int a[maxn],x[maxn],y[maxn];int pos;int f[maxn][5];ll ans;ll search(int aa,int xx,int yy){ if(xx==0&&yy==0) return c[aa]; return min(c[aa],search(xx,f[xx][1],f[xx][2])+search(yy,f[yy][1],f[yy][2]));}int main(){ freopen("dwarf.in","r",stdin); freopen("dwarf.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=m;i++) { int a,x,y; scanf("%d%d%d",&a,&x,&y); f[a][1]=x;f[a][2]=y; } cout<<search(1,f[1][1],f[1][2]); fclose(stdin);fclose(stdout); return 0;}
红字差评系列2.dwarf
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。