曲阜网站建设价格,住房各城乡建设网站,wordpress 网站为什么打不开,有没有房建设计的网站stO 在此给某位靠打01背包处理射程并AC的大神跪了 Orz 问题描述#xff1a; henry公司最近推出了一款新的坦克游戏。在游戏中#xff0c;你将操纵一辆坦克#xff0c;在一个NM的区域中完成一项任务。在此的区域中#xff0c; 将会有许多可攻击的目标… stO 在此给某位靠打01背包处理射程并AC的大神跪了 Orz 问题描述 henry公司最近推出了一款新的坦克游戏。在游戏中你将操纵一辆坦克在一个N×M的区域中完成一项任务。在此的区域中 将会有许多可攻击的目标而你每摧毁这样的一个目标就将获得与目标价值相等的分数。只有获得了最高的分数任务才算完成。 同时为了增加游戏的真实性和难度该游戏还做了以下的限制 (1)坦克有射程r的限制。为方便计算射程r规定为 若坦克位于(x,y)格则它可攻击的目标(x1,y1)必须满足|x-x1|,|y-y1|∈[0,r]。 (2)对坦克完成任务的时间有严格限制规定为t秒。其中坦克每进行一次移动都需1秒的时间每攻击一个目标也需1秒的时 间。时间一到t秒便对此次任务进行记分。 (3)坦克最初位于左上角且移动方向只准是向右或向下每次只允许移动一格。 在以上的限制条件下要完成该任务便成为了一件很难事情。因此你必须为此编写一个程序让它助你完成这个艰巨的任务。 数据范围: 1≤N、M≤501≤r≤101≤t≤250。 输入格式tank.in 第一行四个整数N、M、r、t分别表示区域的长、宽以及射程和完成任务时间。 接下来N行是一个N×M的矩阵对应每个位置上目标的价值。 输出格式(tank.out) 输出文件仅一个数max即该任务中可得到的最高分数。 输入样例 5 5 2 7 0 5 0 0 4 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 5 0 3 0 11 输出样例 21 分析 首先文中提到的每次只能向右向下移动或开炮所以基本上第一印象就是动规所以为了完成动规就会想到下面的 一系列问题 射程是整道题目的关键可以说没有了射程问题就是一道普通的动规题目了直接从1 到 n1 到 m 循环一遍就有结果 了射程是一个r1*r1 的正方形如果每次打掉价值最高的那么就可以完成对射程的处理但于是又引出了下 面的问题 【1】因为对于一个目标是只可以打一次的也就是说这次打过下次就得换一个了所以不同时间同一方块能打到 的最大价值不是固定的要专门开一个数组来记录并不断更新这就是代码的难度直线上升。 【2】其次对于一个决策点xy记上一秒xy-1能达到的最大价值为val1再记上一秒xy 能达到的最大价值为 val2则这一秒在点xy的价值可以是val1也可以是 (val2(此时xy点能打到最大的价值) 如果后者大那么 这么做的话势必会选后者添加进该点但是设此时xy能打到的第二大的价值为 t那么在下一秒同样决策点是 x y由于val2已经打过最大的所以这一秒val2只能打掉次大的所以这时记录的最大价值为val2最大的价值加 次大的价值 但如果上一秒选的是val1这一秒它能达到的价值就是val1最大的价值那么就会存在一种情况 虽然val1val2最大价值但val1val2次大价值那么就会有val1最大价值val2最大价值次大价值 也就是说对于这个决策点xy上一秒的决策是最优但下一秒却不是最优值。这样问题就蛋疼了— — 想到这就应该要做出选择了 【1】放弃动态规划选择和搜索探讨一下感情 — — 不要在一棵树上吊死。。 【2】霸王硬上弓— — 但就必须对射程进行一个可行的判定。直接全范围搜显然是不行的了— — 但强搜显然是会超时的Orz残酷的现实所以如何对射程进行巧妙的处理必不可少这不是废话吗— — 处理射程思路 仔细对每一次移动射程变化的观察会发现每移动一次范围内就会多一组数设决策点为xy若xy由x-1y 向下移 动得到即为从( xry-r 到 yr)的2r个数。这是一个可喜的发现因为严格的讲起来如果对于一个出现在视野内的点马上 把他打掉和之后在把它打掉是没有差别的所以对于这组出现在视野内的数现在就打掉和之后打掉是没差的为了方便编程完 全可以设定为要吗就一进视野就马上打掉要吗就一直都不打。 所以每次要考虑的数就被固定了而且相邻两点要考虑的不会有重合这是非常好的就免去的上面分析中提到的为了判重而 不断更新的问题并且上面分析的前一秒最忧后一秒不一定最优的问题就不存在了。因为做的时候采用一次性添加进要打掉的点 也就是说点是同时添加的影响不大没考虑到也没事只是提到可能会有这种情况。 最后就是要对某个点打k 个目标的得分进行预处理 记le [ i , j , k ]为从左边到达 i j 这个点打掉此时k 个新出现在视野中的目标能获得的得分 记up[ i , j , k ]为从上面到达 i j这个点打掉此时k个新出现在视野中的目标能获得的得分 PS按这个思路一开始要对已经出现在视野内的点进行预处理~~~ 代码: 1 var2 res:array[-20..251,-100..100,-100..100] of longint;//res是进行动规的数组3 //res[该时间横坐标纵坐标]为该时这点得分最大值4 val:array[-20..100,-100..100] of longint; //记录得分点5 up,le:array[0..51,0..51,0..100] of longint; //up,le均为6 n,m,r,t:longint;7 8 Function max(a,b:longint):longint; //求两者最大值得函数返还值为较大者9 begin if ab then exit(a) else exit(b); end;
10
11 Procedure init;
12 var d:array[0..200] of longint;
13 i,j,l:longint;
14 begin
15 l:0;
16 readln(n,m,r,t); //读入行、列、射程、限时
17 fillchar(res,sizeof(res),$ff); //初始化动规数组赋值为-1是为了防止某些不可能情况成立
18 for i:1 to n do
19 for j:1 to m do read(val[i,j]); //读入目标价值
20 for i:1 to r1 do //因为按照思路是考虑视野的边界所以一开始要处理视野内的点
21 for j:1 to r1 do
22 if val[i,j]0 then begin //d数组存放该视野中所有的有分的点的分
23 inc(l);
24 d[l]:val[i,j];
25 end;
26 for i:1 to l-1 do //对这个数组进行排序因为分高的优先去
27 for j:i1 to l do
28 if d[i] d[j] then begin
29 d[0]:d[i]; d[i]:d[j]; d[j]:d[0];
30 end;
31 for i :2 to l do inc(d[i],d[i-1]); //做完这步d[x]表示的就是打掉x 个点的最大得分
32 for i :1 to l do res[i,1,1]:d[i]; //初始化站在原地不动一直打的情况
33 close(input);
34 end;
35
36 Procedure fill; //这个过程就是对每个点的新增视野做类似上方的步骤即预处理
37 var d:array[0..200] of longint;
38 i,j,k,l,p:longint; //l 存的是新增视野内有得分点的数量
39 begin
40 res[0,1,1]:0;
41 for i:1 to n do
42 for j:1 to m do begin //枚举每个点
43 //下面这部分是从上方移动到该点的情况
44 l:0; //清空总数
45 for k:j-r to jr do //查找新增视野中有得分得点
46 if val[ir,k]0 then begin //添加进数组总数1
47 inc(l);
48 d[l]:val[ir,k];
49 end;
50 for k:1 to l-1 do //同样排序
51 for p:k1 to l do
52 if d[k] d[p] then begin
53 d[0]:d[k]; d[k]:d[p]; d[p]:d[0];
54 end;
55 for k:1 to l do up[i,j,k]:up[i,j,k-1]d[k]; //将得到的数据存入up数组中
56 up[i,j,0]:l; //储存最多可以打多少个
57 //这部分是从左方移动到该点的情况
58 l:0; //清空总数
59 for k:i-r to ir do //查找新增视野中有得分得点
60 if val[k,jr]0 then begin //添加进数组总数1
61 inc(l);
62 d[l]:val[k,jr];
63 end;
64 for k:1 to l-1 do //同样排序
65 for p:k1 to l do
66 if d[k] d[p] then begin
67 d[0]:d[k]; d[k]:d[p]; d[p]:d[0];
68 end;
69 for k:1 to l do le[i,j,k]:le[i,j,k-1]d[k]; //将得到的数据存入up数组中
70 le[i,j,0]:l; //储存最多可以打多少个
71 end;
72 end;
73
74 Procedure main;
75 var i,j,z,k:longint;
76 begin
77 for z:1 to t do //把时间做状态
78 for i:1 to n do //枚举每个点
79 for j:1 to m do
80 if ij-2z then begin //边界因为第z 时走到的点 ij与1,1的距离不能超过 z
81 res[z,i,j]:max(res[z-1,i,j],max(res[z-1,i,j-1],res[z-1,i-1,j])); //直接移动来不管新增目标
82 for k:1 to up[i,j,0] do if (z-1-k0)and(res[z-1-k,i-1,j]0) then
83 res[z,i,j]:max(res[z,i,j],res[z-1-k,i-1,j]up[i,j,k]); //枚举打多少个目标从上面来这点的
84 for k:1 to le[i,j,0] do if (z-1-k0)and(res[z-1-k,i,j-1]0) then
85 res[z,i,j]:max(res[z,i,j],res[z-1-k,i,j-1]le[i,j,k]); //枚举打多少个目标从上面左边来的
86 end else break;
87 k:0;
88 for i:1 to n do //循环一边寻找最大值
89 for j:1 to m do
90 if res[t,i,j]k then k:res[t,i,j];
91 writeln(k); //输出结果
92 end;
93
94 begin
95 assign(input,tank.in); assign(output,tank.out);
96 reset(input); rewrite(output);
97 init; fill;
98 main; close(output);
99 end. tank动规打法 优化 虽然根据测试时给的数据都AC的但总耗时还是达到了1.4秒多在完成编程后就可以想想优化 在预处理up和le数组的时候由于每次新出现在视野内的目标不多所以一般采用选择排序但执行次数一多时间就 上去了— —。所以采用快排的打法并进行一定的修改就可以达到0.30秒AC全数据~这边贴一个标程 1 var max,n,m,t,r:longint;2 map,le:array[0..50,0..50] of longint;3 s,temp:array[0..100] of longint;4 f:array[0..50,0..50,0..250] of longint;5 function min(x,y:longint):longint;6 begin7 if xy then min:x else min:y;8 end;9 procedure sort(l,m:longint);10 var i,j,mid,t:longint;11 begin12 i:l;j:m;mid:temp[(lm) div 2];13 repeat14 while temp[i]mid do inc(i);15 while temp[j]mid do dec(j);16 if ij then begin t:temp[i];temp[i]:temp[j];temp[j]:t;inc(i);dec(j);end;17 until ij;18 if im then sort(i,m);19 if jl then sort(l,j);20 end;21 procedure init;22 var i,j,k:longint;23 begin24 assign(input,tank.in);reset(input);25 assign(output,tank.out);rewrite(output);26 readln(n,m,r,t);27 for i:1 to n do28 begin29 for j:1 to m do read(map[i,j]);30 readln;31 end;32 k:0;33 fillchar(temp,sizeof(temp),0);34 fillchar(le,sizeof(le),0);35 max:0;36 for i:1 to r1 do37 for j:1 to r1 do38 begin39 if map[i,j]0 then begin inc(k);40 temp[k]:map[i,j]; end;41 end;42 sort(1,k);43 s[0]:0;44 le[1,1]:k;45 for i:1 to k do s[i]:s[i-1]temp[i];46 if kt then k:t;47 for i:1 to k do begin f[1,1,i]:s[i];if f[1,1,i]max then max:f[1,1,i];end;48 end;49 procedure main;50 var i,j,k,p,ir,il,jr,jl,long,ans:longint;51 begin52 for i:1 to n-r do53 for j:1 to m-r do54 if (i1) or (j1) then55 begin56 if i1 then57 begin58 if irn then ir:ir else ir:n;59 if jrm then jr:jr else jr:m;60 if i-r1 then il:i-r else il:1;61 if j-r1 then jl:j-r else jl:1;62 long:0;63 for k:1 to jr-jl1 do if map[ir,kjl-1]0 then64 begin inc(long);temp[long]:map[ir,kjl-1];end;65 sort(1,long);66 s[0]:0;67 fillchar(s,sizeof(s),0);68 for k:1 to long do s[k]:s[k-1]temp[k];69 ans:min(le[i-1,j]long,t-(ij-2));70 if ansle[i,j] then le[i,j]:ans;71 for k:1 to ans do72 begin73 f[i,j,k]:0;74 for p:0 to min(long,k) do75 begin76 if f[i-1,j,k-p]s[p]f[i,j,k] then77 f[i,j,k]:f[i-1,j,k-p]s[p];78 end;79 if f[i,j,k]max then max:f[i,j,k];80 end;81 end;82 if j1 then83 begin84 if irn then ir:ir else ir:n;85 if jrm then jr:jr else jr:m;86 if i-r1 then il:i-r else il:1;87 if j-r1 then jl:j-r else jl:1;88 long:0;89 for k:1 to ir-il1 do if map[kil-1,jr]0 then90 begin inc(long);temp[long]:map[kil-1,jr];end;91 sort(1,long);92 s[0]:0;93 fillchar(s,sizeof(s),0);94 for k:1 to long do s[k]:s[k-1]temp[k];95 ans:min(le[i,j-1]long,t-(ij-2));96 if ansle[i,j] then le[i,j]:ans;97 for k:1 to ans do98 begin99 for p:0 to min(long,k) do
100 begin
101 if f[i,j-1,k-p]s[p]f[i,j,k] then
102 f[i,j,k]:f[i,j-1,k-p]s[p];
103 end;
104 if f[i,j,k]max then
105 begin max:f[i,j,k];end;
106 end;
107 end;
108 end;
109 writeln(max);
110 close(input);
111 close(output);
112 end;
113 begin
114 init;
115 main;
116 end. tank急速优化版 PS该代码无注释但了解它的思想就看得懂了~ 后记 一、如文章第一句 — — 用01背包处理新出现在视野中的点也是可以A的— —只比优化慢0.2秒。还可以用贪心— —。 反正解决了对视野的处理将其转化为新视野后就八仙过海各显神通啦— — 所以不要拘泥于一种算法— —还是 那句话不要在一棵树上吊死— — 二、总的来说无论是对视野的处理还是解决视野问题后的预处理都让我收获了很多也意识到了自己的很多不足Orz。。 END。 转载于:https://www.cnblogs.com/qq359084415/p/3378274.html
