package srm646; import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; public class TheGridDivTwo { //<1>state的比较函数,是"大于>"即大的在前面,属于降序排序 //<2>比较函数在 score-step,这个是启发是搜索策略,可以让搜索,尽量向右搜索,而不是向左,即有一定的方向性。 //当然,如果直接基于score排序,这也是可以的,但性能应该差一些。 static public class State implements Comparator<State>,Comparable<State> { public State() { } public State(int x, int y, int score) { this.x = x; this.y = y; this.score = score; } int x; int y; int score; int step; @Override public int compare(State o1, State o2) { // TODO Auto-generated method stub if (o1.score-o1.step < o2.score-o2.step) { return 1; } if (o1.score-o1.step == o2.score-o2.step) { return 0; } return -1; } @Override public String toString(){ return "{"+x+","+y+","+score+","+step+"}"; } @Override public int hashCode() { return x ^ y; } @Override public boolean equals(Object src) { return src != null && src instanceof State && ((State) src).x == x && ((State) src).y == y; } @Override public int compareTo(State o) { if (score -step< o.score-step) { return 1; } if (score-step == o.score-step) { return 0; } return -1; } } public int find(int[] x, int[] y, int k) { int ans = 0; Set<State> blockedMap = new HashSet<State>(); for (int i = 0; i < x.length; i++) { blockedMap.add(new State(x[i], y[i], 0)); } State start = new State(); start.x = 0; start.y = 0; start.score = 0; start.step = 0; State maxState = new State(0, 0, 0); PriorityQueue<State> pq = new PriorityQueue<State>(); Set<State> visited = new HashSet<State>(); pq.add(start); visited.add(start); while (!pq.isEmpty()) { State cur = pq.poll(); if (cur.step > k) { continue; } if (maxState.score < cur.score) { maxState.score = cur.score; maxState.x = cur.x; maxState.y = cur.y; maxState.step = cur.step; } //后面的得分会更小(这个是分支限界,剪枝策略) if(cur.score + k - cur.step <= maxState.score){ continue; } if (cur.step < k) { // [cur.x+1][cur.y+1] State next = null; next = new State(cur.x + 1, cur.y, cur.score + 1); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } next = new State(cur.x - 1, cur.y, cur.score -1); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } next = new State(cur.x, cur.y + 1, cur.score); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } next = new State(cur.x, cur.y - 1, cur.score); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } } } System.out.println(maxState); ans = maxState.score; return ans; } public static void main(String args[]) { TheGridDivTwo div2= new TheGridDivTwo(); int ans = div2.find(new int[]{1,1,1,1}, new int[]{-2,-1,0,1},4); System.out.println(ans); ans = div2.find(new int[]{1,0,0,-1,-1,-2,-2,-3,-3,-4,-4}, new int[]{0,-1,1,-2,2,-3,3,-4,4,-5,5},47); System.out.println(ans); } }
这是SRM646 的div2 题,刚开始,比较函数写成了<,后修改为降序排列,但没改正确,检查很多遍都没有发现。
这是一个基本的穷举搜索过程,但在brute-force search中可以加入一些策略,比如启发式的(score-step),这个也算A*,再加入一个限界,用于剪枝
相关推荐
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
SRM2Multi dumper for hsap
2. **SRM服务器**:运行SRM软件的物理或虚拟服务器,操作系统需为Server 2008 x64。 3. **支持SRM的数据库**:这里指能够被SRM兼容的数据库系统,例如SQL Server 2005。该数据库用于存储SRM的相关配置信息。 4. **...
因此,`a[2]`被赋值为2,然后`a[2]`的值(也就是2)被赋给`a[2]`,所以数组的第三个元素值未变。 6. 多级指针数组的内存占用: 定义`int **a[3][4]`表示一个3x4的二维数组,其中每个元素都是指向指针的指针。在32...
BS ISO IEC 24392-2023 网络安全——工业互联网平台安全参考模型(SRM-IIP).rar
SAP SRM 介绍
描述部分简单地重复了标题中的关键词“安装指南”,进一步强调了文档的主要目的——指导用户完成SAP SRM 7.0 EHP2的安装流程。 ### 标签:“sap” 标签“sap”明确了文档的主题是关于SAP软件,这是一个全球领先的...
Driver HASP SRM emulator (x86)
2. OMRON产品命名约定:OMRON公司产品的型号在本手册中都是以大写形式出现,包括“CPM1”,“CPM1A”,“CPM2A”,“CPM2C”,“SRM1(-V2)”等。这可能是为了方便阅读时对产品型号的快速识别。此外,手册中提到的...
答:我不知道这段代码的具体功能,但明显有两个错误1,SRM_no 没有赋初值2,由于 static 的声明,使该函数成为不可重入(即不可预测结果)函数,因为 SRM_no 变量放在程序的全局存储区中,每次调用的时候还可以保持...
根据给定的文件信息,我们将深入探讨“SRM-MDM Catalog Setup – Ready Reference”这一主题,专注于SAP NetWeaver MDM系统中的SRM-MDM目录设置过程。这份文档不仅适用于SAP SRM(Supplier Relationship Management...
《SRM中的中断处理——以"irq_srm.rar_SRM_The Handle"为焦点》 在计算机系统中,中断处理是操作系统核心功能之一,它负责响应硬件设备发送的信号,以便进行相应的处理。当我们谈论"irq_srm.rar_SRM_The Handle"时...
2. **边界长度**:`srm_boundarylen.cpp`可能是用于计算相邻区域边界的长度,这是评估区域合并代价的另一个因素。较长的边界通常意味着更高的合并成本,因为这会引入更多的不确定性。 3. **SRM主程序**:`srm.m`是...
首先,我们关注到主要的函数文件——`SRM_new.m`,这通常是整个程序的入口点,包含了SRM影像分割的主要逻辑。在这个文件中,开发者可能定义了阈值设定、区域合并策略以及其它与分割相关的算法步骤。用户可以根据需求...
### SAP NetWeaver MDM – SRM Catalog Configuration #### 概述 本文档旨在总结配置SRM源系统向MDM系统提供产品目录数据的过程,这些数据将发布到SRM买家门户的EBP前端。文档主要通过截图的形式展示了配置步骤,...
HASP SRM加密狗简介 HASP SRM加密狗是一种软件保护解决方案,由阿拉丁公司开发。它提供了多种型号,以满足不同业务需要。下面将对HASP SRM加密狗的各种型号进行详细介绍。 首先是HASP HL基本型,这是阿拉丁公司最...
【标题】"VSAN与SRM"涉及到的是VMware虚拟化环境中的两个关键组件:Virtual SAN(VSAN)和Site Recovery Manager(SRM)。这两个工具在企业级数据中心中发挥着至关重要的作用,确保业务连续性和灾难恢复能力。 VSAN...
2. 扩展、加强与重要供应商的关系:SRM 能够帮助企业与其建立合作关系,共享计划、产品设计和规范信息,并运作方式上进行改进。 3. 建立竞争优势:SRM 能够主动地帮助企业去建立、改进与供应商之间的战略同盟,不是...