打砖块 gameloft_怎么算红砖的块数公式

     小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下：
     在刚开始的时候，有n行*m列的砖块，小红有k发子弹。小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。
如图所示：

    某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。

    小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗

输入文件

    第一行有3个正整数，n，m，k。表示开始的时候，有n行*m列的砖块，小红有k发子弹。
接下来有n行，每行的格式如下：
     f1 c1 f2 c2 f3 c3 …… fm cm
    其中fi为正整数，表示这一行的第i列的砖，在打碎以后的得分。ci为一个字符，只有两种可能，Y或者N。Y表示有一发奖励的子弹，N表示没有。
    所有的数与字符之间用一个空格隔开，行末没有多余的空格。

输出文件

    仅一个正整数，表示最大的得分。

输入样例

 3 4 2

 9 N 5 N 1 N 8 N

 5 N 5 Y 5 N 5 N

 6 N 2 N 4 N 3 N

输出样例

13

数据范围

对于20%的数据，满足1<=n,m<=5，1<=k<=10，所有的字符c都为N
对于50%的数据，满足1<=n,m<=200，1<=k<=200，所有的字符c都为N
对于100%的数据，满足1<=n,m<=200，1<=k<=200，字符c可能为Y
对于100%的数据，所有的f值满足1<=f<=10000

【题目分析】  对于这道题目，经过分析发现在不考虑子弹奖励的情况下，列与列之间相互并不影响，我们可以在某一列不停的打子弹直到达到我们想要的状态，而如果某一列打完预计的子弹之后剩下的砖块为Y，那么一定要打，可以从其他的子弹中借一颗来打掉它，再用它奖励的子弹去还，由此可见，这道题目具有最优子结构，以列做状态能够保证无后效性，动态规划的算法由此确定，

当没有Y时，状态转移方程可轻易得出，写在下面，不再做详细解释

                       b[j,i]=max{b[j-1,i-k]+s[j,k]}

但是这显然只适用于50%的数据，要想得到满分，必须处理有Y的情况，即要考虑接子弹的情况，而借子弹的与否和得分最大，又取决于前面所有列的最优值和在该行的借子弹情况，在该列的情况又是由在该列不借子弹的情况决定的，所以两种情况都要保存，这里用f1,f2,s1,s2四个数组表示，其含义为：

    f1[j][i]：第j列打i发子弹，最后一个子弹打第j列的砖块。
    f2[j][i]：第j列打i发子弹，最后一个子弹不打第j列的砖块（借子弹的情况）。
    s1[j][i]：前j列打i发子弹，最后一个子弹打第j列的砖块。
    s2[j][i]：前j列打i发子弹，最后一个子弹不打第j列的砖块（借子弹的情况）。

则可以分别得出s1,s2的状态转移方程

   s2[j][i]=Max(s2[j-1][i-k]+f2[j][k]);   （0<=k<=i）

  对于这个状态转移方程是说前j列共打i发子弹能得到的最大得分，为前j-1列打i-k发子弹,在第j列打k发子弹得到的最大分值和，由于都是借子弹，所以s2的更新用s2和f2来更新，显然，在第j列用的子弹数要小于等于前j列用的子弹总数。

   s1[j][i]=Max{s2[j-1][i-k]+f1[j][k],    （k>0）
                         s1[j-1][i-k]+f2[j][k]}    （i-k>0）

  对于这个状态转移方程,有必要仔仔细细的品味，这可以说是这道题目的亮点，首先是对k>0时的解释，s1时不借子弹的情况，但打第j列时，又有了新的子弹，所以可以把前面漏在外面的Y全部打掉，所以这里用s2来更新s1，而这也是k>0的原因，只有在这一列有新子弹才能打前面的Y，如果k=0，那么说明在第j列没有用子弹也就无法再去打前面的Y了。第二种情况，i-k>0时，s1[j-1][i-k]表示在j-1列中一定有一砖块是用我们手上的子弹直接打下来的，如果，该砖块是Y，我们可以打下它后，用奖励的那发子弹去打第j列靠上的Y砖块。如果，该砖块是N，我们可以先用一发子弹去打第j列所要打的Y砖块，用j列最后一个被打下的Y砖块所奖励的子弹去打那个N砖块。所以仅当i-k>=1时（即i-k>0），方程中s1[j-1][i-k]才有意义。

View Code

 1 program game(input,output);
 2 const maxn=201;
 3 var a:array[0..maxn,0..maxn]of longint;
 4     s2,s1,f2,f1:array[0..maxn,0..maxn] of longint;
 5     c:array[0..maxn,0..maxn] of char;
 6     i,j,k,t,n,m,tmp,num:longint;
 7     ch:char;
 8 begin
 9     readln(n,m,num);
10     for i:=1 to n do
11     begin
12      for j:=1 to m do
13       begin
14         read(a[i,j]);
15         read(ch);
16         read(c[i,j]);
17       end;
18       readln;
19     end;
20     for i:=1 to m do
21     begin
22       t:=n;
23       while (t>0)and(c[t,i]='Y') do
24        begin
25         inc(f2[i,0],a[t,i]);
26         dec(t);
27        end;
28       for j:=1 to n do
29        if t>0 then
30         begin
31          f1[i,j]:=f2[i,j-1]+a[t,i];
32          f2[i,j]:=f1[i,j];
33          dec(t);
34          while (t>0)and(c[t,i]='Y') do
35           begin
36             inc(f2[i,j],a[t,i]);
37             dec(t);
38           end;
39         end;
40     end;
41     for j:=1 to m do
42      for i:=0 to num do
43       for k:=0 to n do
44        if k<=i then
45         begin
46          tmp:=s2[j-1,i-k]+f2[j,k];
47          if (tmp>s2[j,i]) then
48           s2[j,i]:=tmp;
49          if (k<i) then
50           begin
51            tmp:=s1[j-1,i-k]+f2[j,k];
52            if (tmp>s1[j,i]) then
53             s1[j,i]:=tmp;
54           end;
55          if (k>0) then
56           begin
57            tmp:=s2[j-1,i-k]+f1[j,k];
58            if tmp>s1[j,i] then
59             s1[j,i]:=tmp;
60           end;
61         end;
62     writeln(s1[m,num]);
63 end.

今天的文章打砖块 gameloft_怎么算红砖的块数公式分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。