区块链技术博客
www.b2bchain.cn

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

这篇文章主要介绍了【周赛总结】BFS,状态压缩DP,三进制轮廓线DP的讲解,通过具体代码实例进行20792 讲解,并且分析了【周赛总结】BFS,状态压缩DP,三进制轮廓线DP的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=20792

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

  • 1653. 使字符串平衡的最少删除次数 M 前后两次遍历
  • 1654. 到家的最少跳跃次数 M BFS
  • 1655. 分配重复整数 H 状态压缩DP
  • 1658. 将 x 减到 0 的最小操作数
  • 1659. 最大化网格幸福感 H 轮廓线DP

这周的周赛可太难了。两道hard题都是偏难的。

1653. 使字符串平衡的最少删除次数 M 前后两次遍历

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

前后两次进行遍历,从前往后遍历中维护一直是a的情况下,需要删除多少b。从后往前遍历过程中,维护一直是b的情况下,需要删除多少a。最后进行一次遍历,找到一个分界点,保证前面都是a,后面都是b。

这种两次遍历的思想维护还是很关键的。

class Solution {     public int minimumDeletions(String s) {         int n = s.length();         int[] amap = new int[n];         int[] bmap = new int[n];         int anum = 0;         int bnum = 0;         for (int i = 0; i<n;i++){             if (s.charAt(i) == 'b'){                 bnum++;             }             bmap[i] = bnum;         }         for (int i = n-1; i>=0; i--){             if (s.charAt(i) == 'a'){                 anum++;             }             amap[i] = anum;         }         int ans = 100000000;         for (int i = 0; i<n; i++){             ans = Math.min(ans, amap[i]+bmap[i]-1);         }         return ans;     } } 

1654. 到家的最少跳跃次数 M BFS

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

方法很类似有一次的LC杯的题目,对于每个点,为了防止重复利用,我们只记录第一次到达该点的信息。

class Solution {     public int minimumJumps(int[] forbidden, int a, int b, int x) {         // BFS方法,维护队列[index, numjump, state]         if (x == 0)return 0;         Queue<int[]> queue = new LinkedList<>();         HashSet<Integer> forbid = new HashSet<>();                  for (int k:forbidden) forbid.add(k);         if (forbid.contains(a)) return -1;                           queue.offer(new int[]{a, 1, 0});         HashSet<Integer> inqueue = new HashSet<>();         inqueue.add(a);                  while (!queue.isEmpty()){             int[] cur = queue.poll();             if (cur[0] == x)return cur[1];              if (cur[2]==0){                 int nextindex = cur[0]-b;                 if (nextindex>0 && !forbid.contains(nextindex) && !inqueue.contains(nextindex)){                     queue.offer(new int[]{nextindex, cur[1]+1, 1});                     inqueue.add(nextindex);                 }             }              int nextindex = cur[0]+a;             // 因为家最远是2000,且最远一次跳2000,因此超过6000可以不用考虑了             if (nextindex< 6000 && !forbid.contains(nextindex) && !inqueue.contains(nextindex)){                 queue.offer(new int[]{nextindex, cur[1]+1, 0});                 inqueue.add(nextindex);             }         }         return -1;     } } 

1655. 分配重复整数 H 状态压缩DP

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

题目的特点是顾客数量不多,因此很容易想到采用状态压缩DP的方法。但是这里其实不好想到如何进行枚举。首先nums中数字的内容其实不重要,关键在于数量。首先我们维护一个nums的数字频次数组。然后我们设计dp[i][state]表示这个前i个数字,能否满足state状,而状态转移方程则需要从一个与这个状态无交集的状态转移得到。而当前数字个数能否满足当前的state状态需要计算当前state的1
的位置需要多少个数字。

class Solution {     public boolean canDistribute(int[] nums, int[] quantity) {        Arrays.sort(nums);         int n = nums.length;         int[] many = new int[60];         int index = 0;         int cnt = 0;         for (int i = 0; i<n;i++ ){             if (i != 0 && nums[i]!=nums[i-1]) {                 many[index] = cnt;                 cnt = 0;                 index++;             }             cnt++;         }         many[index] = cnt;          int m = quantity.length;         int N = 1<<m;         boolean[] dp = new boolean[N];         dp[0]= true;        	// 适用了空间压缩         for (int i = 0; i<=index;i++){ // 枚举不同的数字,分析这个数字可以满足的情况             for (int j = N-1;j>=0;j--){ // 枚举已经满足的集合状态                 if (!dp[j]) continue; // 只能从一个true的状态转移过来。                 for (int k = 0; k<N;k++){ // 枚举当前这个数字可以满足的多个请求                     if ((k&j)>0) continue; // 不能有重合的                     int total = 0;                     for (int l = 0;l<m;l++){ // 枚举当前状态中的1的数字。                         if (((k>>l)&1)==1) total += quantity[l];                     }                     if (many[i]>=total) dp[j|k] = true;                 }             }         }         return dp[N-1];     } } 

1658. 将 x 减到 0 的最小操作数

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

思路是一个转换的思路,需要求两边的短,等价于求解中间的最长。因此采用滑动窗的方法。

class Solution {     public int minOperations(int[] nums, int x) {         int sum = 0;         for (int i:nums)sum+=i;         int n = nums.length;         int target = sum-x;         if (target == 0)return n;         int l = 0;         int r = 0;          int cur = 0;         int ans = 0;         while (r<n && l<n){             if (cur<target){                 cur += nums[r];                 r++;             }else if (cur == target){                 ans = Math.max(ans, r-l);                 cur -= nums[l];                 l++;             }else{                 cur -= nums[l];                 l++;             }         }         if (cur == target)ans = Math.max(ans, r-l);         if (ans == 0)return -1;         return n-ans;               } } 

1659. 最大化网格幸福感 H 轮廓线DP

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

是采用的轮廓线DP的思路,也就是把四个方向变为只考虑两个方向。dp[m*n + 1][a+1][b+1][cases];表示当前的index,剩余的外向人和内向人的数量,以及该位置填入的人。

class Solution {     public int getMaxGridHappiness(int m, int n, int a, int b) {         // 0- 不放人 1-放内向 2-放外向 3^n         int cases = (int)Math.pow(3, n); // 保存了一行的状态,这样可以很快的提取         int cases_1 = (int)Math.pow(3, n-1);         int[][] offset = new int[][]{{0,0,0},{0, -60, -10},{0, -10, 40}};                  int M = cases - 1;         int[][][][] dp = new int[m*n + 1][a+1][b+1][cases];                  for(int coor = m*n-1; coor >= 0; --coor) {             int i = coor / n, j = coor % n;             for(int x = 0; x <= a; ++x) {                 for(int y = 0; y <= b; ++y) {                     for(int pre = 0; pre < cases; ++pre) { // pre 就是前 n 个格子的状态(三进制)                         int nem = (pre * 3) % cases; // nem 是 pre “左移” 一位, 并去掉首位的状态,比如三进制 2121->三进制 1210.                         if(x > 0) {                             int p = 0;                             if (j != 0)p =1; //                              int diff = 120 + p*offset[1][pre % 3] + offset[1][pre / cases_1];                             dp[coor][x][y][pre] = Math.max(dp[coor][x][y][pre], diff + dp[coor + 1][x-1][y][nem + 1]);                         }                         if(y > 0) {                             int p = 0;                             if (j != 0)p =1;                             int diff = 40 + p*offset[2][pre % 3] + offset[2][pre / cases_1];                             dp[coor][x][y][pre] = Math.max(dp[coor][x][y][pre], diff + dp[coor + 1][x][y-1][nem + 2]);                         }                         dp[coor][x][y][pre] = Math.max(dp[coor][x][y][pre], dp[coor + 1][x][y][nem]);                     }                 }             }         }         return dp[0][a][b][0];     } } 

本文转自互联网,侵权联系删除【周赛总结】BFS,状态压缩DP,三进制轮廓线DP

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 【周赛总结】BFS,状态压缩DP,三进制轮廓线DP
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们