首页 > 代码库 > 乌龟棋（noip2010）
乌龟棋（noip2010）
分析：该题是经典的动态规划题目。
题目中涉及到卡片数、卡片分4类、格子数等若干信息,又每张卡片仅能使用一次。求到达终点最多能能获得多少分。
从题目中可知卡片的使用顺序影响最终得分，我们可知状态转移和使用哪种类型的卡片有关，假设我们用i、j、k、L分别表示4类卡片，f表示能获得的最多分数。则有：
f[i,j,k,L]=max{f[i-1,j,k,L],f[i,j-1,K,l],f[i,j,k-1,L],
f[i,j,k,L-1]}+a[i*1+j*2+k*3+L*4+1]
{这是一个四维DP..如果用f[i,j,k,l]表示数值为1的用了i个,数值为2的用了j个,数值为3的用了k个,数值为4的用了l个时能够得到的最大得分...那么对于某一个状态,就可以从四个已知的状态的来,即: f[i,j,k,l]:=max(f[i-1,j,k,l],f[i,j-1,k,l],f[i,j,k-1,l],f[i,j,k,l-1])+a[i*1+j*2+k*3+l*4+1];初始f[0,0,0,0]:=a[1];用sum[i]表示i数值的纸片有多少张...那么目标就是f[sum[1],sum[2],sum[3],sum[4]]}var n,m:longint; a:array[0..400] of longint; sum:array[0..4] of longint; f:array[-1..42,-1..42,-1..40,-1..42] of longint; procedure init; var i,x:longint; begin assign(input,‘tortoise.in‘); reset(input); fillchar(sum,sizeof(sum),0); readln(n,m); for i:=1 to n do read(a[i]); readln; for i:=1 to m do begin read(x); inc(sum[x]);end; end; function max(x,y,z,u:longint):longint; begin if (x>y)and(x>z)and(x>u) then max:=x else if (y>z) and(y>u) then max:=y else if z>u then max:=z else max:=u; end; procedure main; var i,j,l,k,t:longint; begin fillchar(f,sizeof(f),0); f[0,0,0,0]:=a[1]; for i:=0 to sum[1] do for j:=0 to sum[2] do for k:=0 to sum[3] do for l:=0 to sum[4] do begin t:=i+j*2+k*3+L*4+1; f[i,j,k,l]:=max(f[i-1,j,k,l],f[i,j-1,k,l],f[i,j,k-1,l],f[i,j,k,l-1])+a[t]; end; end;begin assign(output,‘tortoise.out‘);rewrite(output); init; main; writeln(f[sum[1],sum[2],sum[3],sum[4]]); close(output);end.
乌龟棋（noip2010）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。