python做网站怎么样,网页制作及网站设计,网站动态好还是静态好,现在做什么网站好技能树(SGOI) skill.pas/c/cpp 【问题描述】 玩过 Diablo 的人对技能树一定是很熟悉的。一颗技能树的每个结点都是一项技能#xff0c;要学会这项技能则需要耗费一定的技能点数。只有在学会了某一项技能以后#xff0c;才能继续学习它的后继技能。每项技能又有着不同的级别要学会这项技能则需要耗费一定的技能点数。只有在学会了某一项技能以后才能继续学习它的后继技能。每项技能又有着不同的级别级别越高效果越好而技能的升级也是需要耗费技能点数的。 有个玩家积攒了一定的技能点数他想尽可能地利用这些技能点数来达到最好的效果因此他给所有技能的所有级别都打上了分他认为效果越好的则分数越高。现在他要你帮忙寻找一个分配技能点数的方案使得分数总和最高。 【输入格式】 第一行是一个整数 n1n20表示所有不同技能的总数。接下来依次给出了这 n 个不同技能的详细描述。每个技能描述共包括 5 行第一行是该技能的名称第二行是该技能在技能树中的父技能的名称为空则表示该技能不需要任何的先修技能便能学习。第三行是一个整数 L1L20 表示这项技能所拥有的最高等级。第四行共有 L 个整数其中第 i 个整数表示把这项技能从第 i-1 级升到第 i 级所需要的技能点数0级表示没有学习过。第五行也包括了 L 个整数其中第 i个整数表示该玩家对这项技能的第 i 级的效果评分分数不超过 20。在技能描述之后是玩家所用角色的描述共有两行。第一行是一个整数 P0P100表示目前所拥有的技能点数。接下来一行是 n 个整数依次表示角色当前所习得的技能级别0 表示尚未学习。这里 不会出现非法的情况譬如在没有学习某项技能的时候已经习得了它的后继技能。 【输出格式】 只需包括一个整数 S表示你的技能点最佳分配方案所得到的分数总和。 【输入样例】 3 Freezing Arrow Ice Arrow 3 3 3 3 15 4 6 Ice Arrow Cold Arrow 2 4 3 10 17 Cold Arrow 3 3 3 2 15 5 2 10 0 0 1 【输出样例】 42 【时间限制】 1s 【空间限制】 64M //------------------------------------------------------------------------------------------------ 分析:树形动规,多叉树转二叉树. f[i,j]表示以i为根的子树,花j点技能点,能得到的最大分数. 枚举给左右儿子分配的点数进行转移,记忆化搜索. code: type skillrecordn,f:string;l:longint;v,p:array[0..21] of longint;
end;
const maxn21;maxp101;
var s:array[0..maxn] of skill;f:array[0..maxn,0..maxp] of longint;learn,l,r:array[0..maxn] of longint;n,i,j,fa,tmp,p,ans:longint;function find(st:string):longint;var o:longint;beginfor o:1 to n doif s[o].nst then exit(o);exit(0);end;function maxx(a,b:longint):longint;beginif ab then exit(a); exit(b);end;function DP(t,m:longint):longint;var max,now,o,cost,value,q:longint;beginif f[t,m]0 then exit(f[t,m]);max:DP(r[t],m); //不学这种技能if learn[t]0 then //已经学过的话,向下接着学for o:1 to m dobeginnow:DP(l[t],o)DP(r[t],m-o);max:maxx(max,now);end;cost:0;value:0;for o:learn[t]1 to s[t].l do //把这个技能接着学下去begincost:costs[t].v[o];value:values[t].p[o];for q:0 to m-cost dobeginnow:DP(l[t],q)DP(r[t],m-cost-q)value;max:maxx(max,now);end;end;f[t,m]:max;exit(max);end;beginassign(input,skill.in); reset(input);assign(output,skill.out); rewrite(output);readln(n);for i:1 to n dobeginreadln(s[i].n);readln(s[i].f);readln(s[i].l);for j:1 to s[i].l do read(s[i].v[j]);readln;for j:1 to s[i].l do read(s[i].p[j]);readln;end;readln(P);for i:1 to n do read(learn[i]);for i:1 to n dobeginfa:find(s[i].f);if l[fa]0 then l[fa]:ielsebegintmp:l[fa];while r[tmp]0 do tmp:r[tmp];r[tmp]:i;end;end;fillchar(f,sizeof(f),255);for i:0 to maxp do f[0,i]:0;ans:DP(l[0],P);writeln(ans);close(input);close(output);
end.转载于:https://www.cnblogs.com/exponent/archive/2011/08/06/2129483.html
