本文主要是介绍ABC345 D Tiling 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
DTiling：
题目大意：
思路解析：
可以发现总共只有7个方块，那么使用这七个方块填充整个地图的可能性只有128种组合，然后每次填充之后遍历100个格子并且判断以这个点作为图块的左上角能不能满足约束条件，那么时间复杂度128*100*100 * 2，有这么多可放的情况，如果每个情况都新建一个地图，那么时间复杂度为128 * 100 * 100 * 2 * 100因为这个时间复杂度是最坏情况下，不一定能到达最坏情况，但是有可能会超时，所以我们应该利用dfs，然后重复利用一个数组，并且在图块选择时，也应该先使用大的图块，这样可以减少大量枚举点，减少超时的可能。
代码实现：
import java.io.*;
import java.util.*;public class Main {public static int INF = 0x3f3f3f3f, mod = 1000000007, mod9 = 998244353;public static void main(String args[]){try {PrintWriter o = new PrintWriter(System.out);boolean multiTest = false;// initif(multiTest) {int t = nextInt(), loop = 0;while (loop < t) {loop++;solve(o);}} else solve(o);o.close();} catch (Exception e) {e.printStackTrace();}}static int n, h, w;static int[] a, b, preSum;static void solve(PrintWriter o) {try {n = nextInt();h = nextInt();w = nextInt();a = new int[n];b = new int[n];List<int[]> li = new ArrayList<>();for(int i=0;i<n;i++) {a[i] = nextInt();b[i] = nextInt();li.add(new int[]{a[i], b[i]});}// 先填大的块 如果大的不满足再填小的块，这样如果只要填充了大块，就可以减少大量搜寻可能性Collections.sort(li, (x,y)->-Integer.compare(x[0]*x[1], y[0]*y[1]));for(int i=0;i<n;i++) {a[i] = li.get(i)[0];b[i] = li.get(i)[1];}preSum = new int[n+1];for(int i=1;i<=n;i++) preSum[i] = preSum[i-1]+a[i-1]*b[i-1]; // 利用前缀和计算剩余的图块面积为多少boolean[][] table = new boolean[h][w];boolean ok = dfs(0, table, h*w);if(ok) o.println("Yes");else o.println("No");} catch (Exception e) {e.printStackTrace();}}static boolean abort = false;static boolean dfs(int i, boolean[][] table, int remain) {if (abort) return true;if(preSum[n]-preSum[i] < remain) return false;if(i >= n) return remain == 0;boolean ok = false;for(int x=0;x<h;x++) for(int y=0;y<w;y++) {if(can(x, y, i, table)) { // 有两种放的情况place(x, y, i, table);remain -= a[i]*b[i];ok |= dfs(i+1, table, remain);remain += a[i]*b[i];if(ok) abort = true;unplace(x, y, i, table);}if(can2(x, y, i, table)) {place2(x, y, i, table);remain -= a[i]*b[i];ok |= dfs(i+1, table, remain);remain += a[i]*b[i];if(ok) abort = true;unplace2(x, y, i, table);}}ok |= dfs(i+1, table, remain);if(ok) abort = true;return ok;}static boolean can(int x, int y, int i, boolean[][] table) {boolean ok = true;if(x+a[i] > h || y+b[i] > w) return false;for(int p=x;p<x+a[i];p++) for(int q=y;q<y+b[i];q++) {if(table[p][q]) {ok = false;break;}}return ok;}static void place(int x, int y, int i, boolean[][] table) {for(int p=x;p<x+a[i];p++) for(int q=y;q<y+b[i];q++) table[p][q] = true;}static void unplace(int x, int y, int i, boolean[][] table) {for(int p=x;p<x+a[i];p++) for(int q=y;q<y+b[i];q++) table[p][q] = false;}static boolean can2(int x, int y, int i, boolean[][] table) {boolean ok = true;if(x+b[i] > h || y+a[i] > w) return false;for(int p=x;p<x+b[i];p++) for(int q=y;q<y+a[i];q++) {if(table[p][q]) {ok = false;break;}}return ok;}static void place2(int x, int y, int i, boolean[][] table) {for(int p=x;p<x+b[i];p++) for(int q=y;q<y+a[i];q++) table[p][q] = true;}static void unplace2(int x, int y, int i, boolean[][] table) {for(int p=x;p<x+b[i];p++) for(int q=y;q<y+a[i];q++) table[p][q] = false;}public static int upper_bound(List<Integer> a, int val){int l = 0, r = a.size();while(l < r){int mid = l + (r - l) / 2;if(a.get(mid) <= val) l = mid + 1;else r = mid;}return l;}public static int lower_bound(List<Integer> a, int val){int l = 0, r = a.size();while(l < r){int mid = l + (r - l) / 2;if(a.get(mid) < val) l = mid + 1;else r = mid;}return l;}public static long gcd(long a, long b){return b == 0 ? a : gcd(b, a%b);}public static long lcm(long a, long b){return a / gcd(a,b)*b;}public static long qpow(long a, long n, int md){a %= md;long ret = 1l;while(n > 0){if((n & 1) == 1){ret = ret * a % md;}n >>= 1;a = a * a % md;}return ret;}public static class FenWick {int n;long[] a;long[] tree;public FenWick(int n){this.n = n;a = new long[n+1];tree = new long[n+1];}private void add(int x, long val){while(x <= n){tree[x] += val;x += x&-x;}}private void addMx(int x, long val) {a[x] += val;tree[x] = a[x];while(x <= n) {for(int i=1;i<(x&-x);i<<=1) {tree[x] = Math.max(tree[x], tree[x-i]);}x += x&-x;}}private long query(int x){long ret = 0l;while(x > 0){ret += tree[x];x -= x&-x;}return ret;}private long queryMx(int l, int r) {long res = 0l;while(l <= r) {if(r-(r&-r) >= l) {res = Math.max(res, tree[r]);r -= r&-r;}else {res = Math.max(res, a[r]);r--;}}return res;}}public static class Pair{Integer c1;String str;public Pair(Integer c1, String str) {this.c1 = c1;this.str = str;}@Overridepublic int hashCode() {int prime = 31, ret = 1;ret = ret*prime + c1.hashCode();return ret;}@Overridepublic boolean equals(Object obj) {if(obj instanceof Pair) {return c1.equals(((Pair) obj).c1);}return false;}}private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));private static StringTokenizer tokenizer = new StringTokenizer("");private static String next() throws IOException{while(!tokenizer.hasMoreTokens()){tokenizer = new StringTokenizer(reader.readLine());}return tokenizer.nextToken();}public static int nextInt() throws IOException {return Integer.parseInt(next());}public static Long nextLong() throws IOException {return Long.parseLong(next());}public static double nextDouble() throws IOException {return Double.parseDouble(next());}public static char nextChar() throws IOException {return next().toCharArray()[0];}public static String nextString() throws IOException {return next();}public static String nextLine() throws IOException {return reader.readLine();}
}这篇关于ABC345 D Tiling 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
