迭代加深-加成序列、双向DFS-送礼物、IDA*-排书、 回转游戏

满足如下条件的序列 X序列中元素被标号为 1、2、3…m被称为“加成序列”X[1]1X[m]nX[1]X[2]…X[m−1]X[m]对于每个 k2≤k≤m都存在两个整数 i 和 j 1≤i,j≤k−1i 和 j 可相等使得 X[k]X[i]X[j]。你的任务是给定一个整数 n找出符合上述条件的长度 m 最小的“加成序列”。如果有多个满足要求的答案只需要找出任意一个可行解。输入格式输入包含多组测试用例。每组测试用例占据一行包含一个整数 n。当输入为单行的 0 时表示输入结束。输出格式对于每个测试用例输出一个满足需求的整数序列数字之间用空格隔开。每个输出占一行。数据范围1≤n≤100输入样例5 7 12 15 77 0输出样例1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { static int N200,id1,id11,n,m; static int a[]new int[N]; static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { String line; while(!(linebr.readLine()).equals(0)){ nInteger.parseInt(line); if(n1){ bw.write(1\n); continue; } a[1]1; for (int m 2; m n; m) { // a[m]n;f[n]true; if(dfs(2,m,n,1)){ break; } // a[m]0;f[n]false; } } bw.flush(); br.close(); bw.close(); } static boolean dfs(int k,int m,int n,int maxz) throws IOException { if(km){ for (int i 1; i m; i) { for (int j 1; j m; j) { if(a[i]a[j]n){ StringBuilder stringBuildernew StringBuilder(); for (int g 1; g m; g) { stringBuilder.append(a[g] ); } stringBuilder.append(n); bw.write(stringBuilder.toString()\n); bw.flush(); return true; } } } return false; } for (int i k-1; i 0; i--) { for (int j k-1; j 0; j--) { if(a[i]a[j]maxz a[i]a[j]n){ a[k]a[i]a[j]; if(dfs(k1, m,n,a[k]))return true; a[k]0; } } } return false; } }送礼物达达帮翰翰给女生送礼物翰翰一共准备了 N 个礼物其中第 i 个礼物的重量是 G[i]。达达的力气很大他一次可以搬动重量之和不超过 W 的任意多个物品。达达希望一次搬掉尽量重的一些物品请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。输入格式第一行两个整数分别代表 W 和 N。以后 N 行每行一个非负整数表示 G[i]。输出格式仅一个整数表示达达在他的力气范围内一次性能搬动的最大重量。数据范围1≤N≤46,1≤W≤231−1,0≤G[i]≤231−1输入样例20 5 7 5 4 18 1输出样例19import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int N200,id1,id11,n,m,k,cnt; static long w,res0; static long weight[]new long[124]; static long a[]new long[N]; // static int group[]new int[N]; static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); wLong.parseLong(st.nextToken()); nInteger.parseInt(st.nextToken()); for (int i 0; i n; i) { a[i]Integer.parseInt(br.readLine()); } //动态规划求解会超出应int的范围而且时间复杂度太高 //所以可以写一个递归版的动态规划 //但是如果我们暴力的去求解一到n那这样必然会超时 //我们可以先暴力的枚举1~n/2 然后再去暴力的枚举后半部分 //当后半部分枚举完之后 我们可以2分前半部分的结果 //从而找到最终的最大值 kn/2; dfs1(0,0); //排序加去重 Arrays.sort(weight,0,cnt); unique(); dfs2(k,0); bw.write(res); bw.flush(); br.close(); bw.close(); } static void unique(){ int cur1; for (int i 1; i cnt; i) { if(weight[i]!weight[i-1]){ weight[cur]weight[i]; } } cntcur; } static void dfs2(int u,long s){ if(un){ int l0,rcnt-1; while(lr){ int mid(lr1)1; if(sweight[mid]w){ lmid; }else{ rmid-1; } } resMath.max(res, sweight[l]); return; } if(sa[u]w)dfs2(u1, sa[u]); dfs2(u1, s); } static void dfs1(int u,long s){//枚举到第u件物品了,总和为s if(uk){ weight[cnt]s; return; } if(sa[u]w)dfs1(u1, sa[u]); dfs1(u1, s); } }排书给定 n 本书编号为 1∼n。在初始状态下书是任意排列的。在每一次操作中可以抽取其中连续的一段再把这段插入到其他某个位置。我们的目标状态是把书按照 1∼n 的顺序依次排列。求最少需要多少次操作。输入格式第一行包含整数 T表示共有 T 组测试数据。每组数据包含两行第一行为整数 n表示书的数量。第二行为 n 个整数表示 1∼n 的一种任意排列。同行数之间用空格隔开。输出格式每组数据输出一个最少操作次数。如果最少操作次数大于或等于 5 次则输出5 or more。每个结果占一行。数据范围1≤n≤15输入样例3 6 1 3 4 6 2 5 5 5 4 3 2 1 10 6 8 5 3 4 7 2 9 1 10输出样例2 3 5 or more解题思路:1. 操作分析与搜索框架每次操作可以抽取任意长度的连续一段插入到任意位置。这样一次操作会改变序列的局部顺序可能同时修正多处错位。直接暴力搜索状态空间会爆炸但观察到最少操作次数被限制在很小的范围≤4≤4 才需要精确值所以可以采用迭代加深IDDFS配合启发式估价A即IDA算法。我们从深度上限max_depth 0开始每次max_depth在 DFS 中一旦当前深度 估价函数值 上限就立即回溯直到找到解或上限达到 5 停止。2. 估价函数的设计估价函数需要给出“从当前状态到目标状态至少还需要多少步”。一次剪切插入操作最多能同时修正多少处“不连续”的错误考察相邻关系若排列中a[i] 1 a[i1]则这一对是“正确的后继”否则是“错误的后继”。目标状态有 n−1n−1 对正确的后继1→2,2→3,…,n−1→n1→2,2→3,…,n−1→n。一次剪切插入操作最多能改变3 个位置的后继关系被剪切段的前后、插入点的前后。因此最多可以修复 3 个错误后继。设当前排列的错误后继个数为cnt则最少还需要⌈cnt/3⌉⌈cnt/3⌉ 步。这就是启发式下界。实际编码时f() cnt / 3即可当cnt0时自然为 0。3. 剪枝与搜索策略为了避免重复搜索对称操作可以规定只将抽取段向后移动。因为把 A 段移动到 B 之前等价于把 B 段移动到 A 之后所以只枚举“把段插入到更后面的位置”就能覆盖所有情况。具体枚举方式枚举抽取段的长度len1∼n−11∼n−1 或 1∼n1∼n。枚举抽取的起始位置l得到区间[l, r]r llen-1。枚举插入位置kk在r之后表示将该段插入到原来第k个元素之后即r1 \sim k这些元素整体前移然后跟上原[l, r]段。这样生成的每个新状态都是唯一的且不会遗漏任何本质不同的操作。递归前备份当前序列到数组na[depth]递归结束后恢复保证回溯正确。4. 终止条件若check()成立即序列完全有序返回成功。若depth f() max_depth立即剪枝返回失败。若max_depth 5仍未找到解直接输出5 or more。5. 时间复杂度n≤15n≤15深度上限最多为 4。分枝数对于每个状态长度有 O(n)O(n) 种起点 O(n)O(n)插入点 O(n)O(n)总约 O(n3)O(n3)但加上启发式剪枝后实际访问的状态数非常少完全可以通过。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N20,id1,id11,n,m,k,cnt,t; static long w,res0; static int na[][]new int[5][N];//记录递归过程中的a 方便恢复现场 static int a[]new int[N]; // static int group[]new int[N]; static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { tInteger.parseInt(br.readLine()); //StringTokenizer stnew StringTokenizer(br.readLine()); for (int i 0; i t; i) { nInteger.parseInt(br.readLine()); StringTokenizer stnew StringTokenizer(br.readLine()); for (int j 0; j n; j) { a[j]Integer.parseInt(st.nextToken()); } int depth0; while(depth5 !dfs(0,depth))depth; if(depth5){ bw.write(depth\n); }else{ bw.write(5 or more\n); } } bw.flush(); br.close(); bw.close(); } static boolean check(){ for (int i 0; i1 n; i) { if(a[i]1!a[i1])return false; } return true; } static int f(){ //每次最多修复3对相邻的关系 int sum0; for (int i 0; i1 n; i) { if(a[i]1!a[i1])sum; } if(sum0)return 0; return sum/31;//最少需要操作这么多次 } static boolean dfs(int depth,int maxdepth){ if(depthf()maxdepth)return false;//f是一个预估函数 if(check())return true; for (int len 1; len n; len) { //把A段放在B之后 和 B段放在A之前是一样的 所以统一向后放 for (int l 0; l n; l) { int rllen-1; //把l-r这一段放在k的后面 System.arraycopy(a, 0, na[depth], 0, n); for (int k r1; k n; k) { //先把r1 到k 移到l开始的位置 再添加l-r的值 int yl; for (int i r1; i k; i) { a[y]na[depth][i]; } for (int i l; i r; i) { a[y]na[depth][i]; } if(dfs(depth1, maxdepth))return true; System.arraycopy(na[depth], 0, a, 0, n);//恢复现场 } } } return false; } }回转游戏如下图所示有一个#形的棋盘上面有 1,2,3 三种数字各 8 个。给定 8 种操作分别为图中的 A∼H。这些操作会按照图中字母和箭头所指明的方向把一条长为 7 的序列循环移动 1 个单位。例如下图最左边的#形棋盘执行操作 A 后会变为下图中间的#形棋盘再执行操作 C 后会变成下图最右边的#形棋盘。给定一个初始状态请使用最少的操作次数使#形棋盘最中间的 8 个格子里的数字相同。输入格式输入包含多组测试用例。每个测试用例占一行包含 24 个数字表示将初始棋盘中的每一个位置的数字按整体从上到下同行从左到右的顺序依次列出。输入样例中的第一个测试用例对应上图最左边棋盘的初始状态。当输入只包含一个 0 的行时表示输入终止。输出格式每个测试用例输出占两行。第一行包含所有移动步骤每步移动用大写字母 A∼H 中的一个表示字母之间没有空格如果不需要移动则输出No moves needed。第二行包含一个整数表示移动完成后中间 8 个格子里的数字。如果有多种方案则输出字典序最小的解决方案。输入样例1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 0输出样例AC 2 DDHH 2import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N20,id1,id11,n,m,k,cnt,t; static long w,res0; /* 一 二 0 1 2 3 八 4 5 6 7 8 9 10 三 11 12 七 13 14 15 16 17 18 19 四 20 21 22 23 六 五 */ static int a[][]{ {0,2,6,11,15,20,22},{1,3,8,12,17,21,23},{10,9,8,7,6,5,4}, {19,18,17,16,15,14,13},{23,21,17,12,8,3,1},{22,20,15,11,6,2,0}, {13,14,15,16,17,18,19},{4,5,6,7,8,9,10} }; static int center[]{6,7,8,11,12,15,16,17};//中心几个点的就是坐标 static int opposite[]{5,4,7,6,1,0,3,2};//存相互抵消的操作 比如说a和b static int q[]new int[24]; static int path[]new int[100]; static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { //tInteger.parseInt(br.readLine()); //StringTokenizer stnew StringTokenizer(br.readLine()); String line; while(!(linebr.readLine()).equals(0)){ StringTokenizer stnew StringTokenizer(line); for (int i 0; i 24; i) { q[i]Integer.parseInt(st.nextToken()); } int depth0; while(!dfs(0,depth,-1))depth; if(depth0){ bw.write(No moves needed\n); bw.write(q[6]\n); continue; } StringBuilder stringBuildernew StringBuilder(); for (int i 0; i depth; i) { stringBuilder.append((char)(path[i]A)); } bw.write(stringBuilder.toString()\n); bw.write(q[6]\n); } bw.flush(); br.close(); bw.close(); } static int f(){ int sum[]new int[4]; for (int i 0; i 8; i) { sum[q[center[i]]]; } //每次移动我会最多会移进来一个新的数 //先统计中间的那几个点次数最多的数是多少 然后用八减去这个值就是预估值你好 int cnt0; for (int i 1; i 4; i) {//只有1~3这几个数字 cntMath.max(cnt, sum[i]); } return 8-cnt; } static void operate(int u){ //每次操作都相当于是将第一个移到最后然后把剩下的前移 int tq[a[u][0]]; for (int i 1; i 7; i) { q[a[u][i-1]]q[a[u][i]]; } q[a[u][6]]t; } static boolean dfs(int depth,int maxdepth,int last){ if(depthf()maxdepth)return false; if(f()0)return true; for (int i 0; i 8; i) { if(opposite[i]last)continue; operate(i); path[depth]i; if(dfs(depth1, maxdepth, i))return true; operate(opposite[i]);//恢复现场 } return false; } }