DAY24

怼烎@ 2023-10-15 00:46 95阅读 0赞

## 题目一 ##

![4f7441f8c03943d89cf760af163d35fe.png][]

啊 看着挺复杂 其实很简单

第一种方法

就是纵轴是怪兽编号 横轴是能力值

看看能不能打过

逻辑很简单 看看能不能打得过 打过的就在花钱和直接打里面取小的 打不过就只能花钱

这种方法就导致 如果怪兽的能力值很大 那么我们就需要很大的空间

所以引出下一种做法

纵轴是怪兽编号 横轴是钱数

我们对比一下这两种方法

1.当能力值大 钱小的情况 第一种方法浪费空间 第二种不浪费

2.当能力值小 钱多的情况 第二种浪费 第一种不浪费

所以 根据数况来取

dp\[i\]\[j\] 表示正好花j元能不能打过怪兽 打不过-1 打得过就是你目前的能力值

状态转移

如果 dp\[i-1\]\[j\]位置的值 大于等于当前怪兽的 能力值 那么dp\[i\]\[j\]==dp\[i-1\]\[j\]

如果 不大于等于 那看这个怪兽 假如说能力值是x 那就得找dp\[i-1\]\[j-x\]的值 然后加上怪兽的能力

就是说 我看看打到上一个怪兽 最少需要多少钱 那么我再加上多少钱就是打败这个怪兽的值

### 方法一 ###

public static long process(int[] d, int[] p, int ability, int index) {
    		if (index == d.length) {
    			return 0;
    		}
    		if (ability < d[index]) {
    			return p[index] + process(d, p, ability + d[index], index + 1);
    		} else { // 可以贿赂，也可以不贿赂
    			return 
    					Math.min(
    							p[index] + process(d, p, ability + d[index], index + 1),
    						    process(d, p, ability, index + 1)
    							);
    		}
    	}
    
    	public static long func1(int[] d, int[] p) {
    		return process(d, p, 0, 0);
    	}

这局部最优整体也最优吗 我想想 如果当前选择了直接打这个怪兽而获得它的能力 正好导致下一个很贵的怪兽必须花钱买怎么办

2 2 1 5

2 花钱 2直接打 1直接打 5花钱 7块

2买 2买 1买 5打 花五块

我开始以为的递归是 每一步局部最优2 花钱 2直接打 1直接打 5花钱 7块 就像这种

但实际的流程是 用动态规划来看 我这个点的钱数 是依赖于前面的最少花的钱数再加上此点最少花的钱数

动态规划

public static long func2(int[] d, int[] p) {
    		int sum = 0;
    		for (int num : d) {
    			sum += num;
    		}
    		long[][] dp = new long[d.length + 1][sum + 1];
    		for (int i = 0; i <= sum; i++) {
    			dp[0][i] = 0;
    		}
    		for (int cur = d.length - 1; cur >= 0; cur--) {
    			for (int hp = 0; hp <= sum; hp++) {
    				// 如果这种情况发生，那么这个hp必然是递归过程中不会出现的状态
    				// 既然动态规划是尝试过程的优化，尝试过程碰不到的状态，不必计算
    				if (hp + d[cur] > sum) {
    					continue;
    				}
    				if (hp < d[cur]) {
    					dp[cur][hp] = p[cur] + dp[cur + 1][hp + d[cur]];
    				} else {
    					dp[cur][hp] = Math.min(p[cur] + dp[cur + 1][hp + d[cur]], dp[cur + 1][hp]);
    				}
    			}
    		}
    		return dp[0][0];
    	}

这个动态规划怎么考虑 感觉从原来的 递归考虑好一点 直接改就可以了 也就是第一层递归出结果 dp\[0\]\[0\] 我把这个任务交给你..... 这压根就是递归硬改的动态规划(精细化搜索)

和正常的从左往右尝试模型有什么不同呢?之前是一个数(钱 或者 容量)越来越少 现在是从零开始越来越多

也为我提供了个思路 不行直接写递归 再改动态规划 复习一下 本质上动态规划使用数组保存结果 减少计算次数

### 方法二 ###

这次横轴是钱 dp\[i\]\[j\]的位置表示严格花j块钱 通过了0....i的怪物获得的最大能力值

严格花j元 那就是说多了也不行 8块钱能通过j==9都不行

然后推到最后一行 从左后一行里面找最左面不为-1的值

最后一行的意义是 解决掉所有怪物花的钱数 我们实际上遍历了所有可以解决掉所有怪物的方法

为什么是严格花多少钱也就出在这里

如果不是严格花多少多少钱 我们最后得出来的结果就不是 解决掉怪物的所有可能了 每一步递推过来就是错的

如果不是严格的 就说明这种组合是无效的 大于也不行 大于抓过的结果 我们之前肯定花很少的钱抓过了 而且我们最后需要的答案是每一种组合 花钱最少的 不严格算是什么样子 在某些情况下不严格不一定是错的 但是严格一定是对的

> 不可置否的乱写
> 
> 假如说我dp\[i\]\[j\] 位置往前找dp\[i - 1\]\[j - p\[i\]\] 它是说打上一个怪物花了这么些钱能打过 它不为-1我们就加上了 i-1怪兽要10块钱 然后我们是不严格的 dp\[j-p\[i\]\]打到+11的位置上面了 本来应该是-1 现在不为-1 那我们这个位置就变成了直接花钱买 因为是取武力值大的 所以直接当前武力值加上 作为结果
> 
> 但实际上 这个位置的结果是不可以加上武力值的 就是说 我们不能严格花这个钱解决这个怪兽
> 
> 如果这个位置是底层的第一个不为-1 那么寄

public static int func(int [] d,int [] p) {
    		int sum = 0;
    		for (int i : p) {
    			sum += i;
    		}
    		int [][] dp = new int [d.length+1][sum+1];
    		for(int i = 0;i<d.length;i++) {
    			for(int j = 0;j<sum+1;j++) {
    				dp[i][j] = -1;
    			}
    		}
    		dp[0][p[0]] = d[0];//第一行只有这个位置有值
    		for(int i = 1;i<d.length;i++) {
    			for(int j = 0;j<sum+1;j++) {
    				if(j>=p[i]&&dp[i - 1][j - p[i]] != -1){//j-p[i]不越界
    					dp[i][j] = dp[i - 1][j - p[i]] + d[i];
    				}
    				if(dp[i-1][j]>=d[i]) {
    					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
    				}//为什么要取一个能力最大的呢 这个位置的钱已经定好了 我就一定花这么多钱 为啥不取个能力大的
    				//这里不用担心 哎呀 我直接买 那岂不是肯定比不买的能力值大吗 注意 这里的钱是一定的 如果这个没买 那么就有其他的钱花在别处
    			}
    		}
    		int ans = 0;
    		for (int j = 0; j <= sum; j++) {
    			if (dp[d.length - 1][j] != -1) {
    				ans = j;
    				break;
    			}
    		}
    		return ans;
    	}

## 题目二 ##

给你一个字符串 `s` ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 `s` 成为回文串的 **最少操作次数** 。

来一个dp数组 纵轴是L 横轴是R dp\[i\]\[j\]表示i...j上需要添加多少字符

每个依赖为: 如果i位置字符等于j位置字符 那么不需要添加 =

如果不等于 那就要看看是在末尾补还是在头部补的操作次数少了

我自己用acbca推了一遍 就是说 当L=0 R=4 的时候怎么求 如果我a==a那就看cbc是怎么变回文的

acb怎么变回文 那就要看ac是怎么变的 cb是怎么变的 在除去开头/结尾的情况下先把它变成回文 然后我们只需要考虑这不是回文的一个字符(就是加上)就可以了

我之前比较困惑的是bab 如果 我在做ba的时候 我直接在后面加了一个b 那我还要也就是变成了bab 已经是回文了 那我这个原本的b怎么处理呢?

如果是bab 在推ba的时候 我们或许会在前面加a 或许会在后面补b 但是如果b==a了 那我们就要看a是怎么变回文串的 而不是ba怎么变的

## 第三题 ##

一种消息接收并打印的结构设计已知一个消息流会不断地吐出整数1~N,但不一定按照顺序吐出。如果上次打印的数为i，那么当i+1出现时，请打印i+1及其之后接收过的并且连续的所有数，直到1~N全部接收并打印完，请设计这种接收并打印的结构。初始时默认i==0

多个空间

比如最开始我们加入 1 3 5 7四个点

那就模拟四个空间

1开头1结尾的

3开头3结尾的

5开头5结尾的

7开头7结尾的

假如说我们来了一个6 它的开头就是6 那我们就去找结尾为5的区间 把他们连在一起

同时维护一个指针 这个指针是指播放到哪个位置了 在哪里卡住了

class Node {
    	public String info;
    	public Node next;
    
    	public Node(String str) {
    		info = str;
    	}
    }
    
    class Messagebox {
    	private HashMap<Integer, Node> headMap;
    	private HashMap<Integer, Node> tailMap;
    	private int waitPoint;
    	
    	public Messagebox() {
    		headMap = new HashMap<Integer, Node>();
    		tailMap = new HashMap<Integer, Node>();
    		waitPoint = 1;
    	}
    	
    	public void receive(int num, String info) {
    		if (num < 1) {
    			return;
    		}
    		Node cur = new Node(info);
    
    		headMap.put(num, cur);
    		tailMap.put(num, cur);
    		// 建立了num~num这个连续区间的头和尾
    		// 查询有没有某个连续区间以num-1结尾
    		if (tailMap.containsKey(num - 1)) {
    			tailMap.get(num - 1).next = cur;
    			tailMap.remove(num - 1);//如果它能接在某个区间的尾部
    			headMap.remove(num);
    		}
    		// 查询有没有某个连续区间以num+1开头的
    		if (headMap.containsKey(num + 1)) {
    			cur.next = headMap.get(num + 1);
    			tailMap.remove(num);//如果它能接在某个区间的头部
    			headMap.remove(num + 1);
    		}
    		if (num == waitPoint) {
    			print();
    		}
    	}
    	
    	private void print() {
    		Node node = headMap.get(waitPoint);
    		headMap.remove(waitPoint);
    		while (node != null) {
    			System.out.print(node.info + " ");
    			node = node.next;
    			waitPoint++;
    		}
    		tailMap.remove(waitPoint-1);
    		System.out.println();
    	}
    }

[4f7441f8c03943d89cf760af163d35fe.png]: https://img-blog.csdnimg.cn/4f7441f8c03943d89cf760af163d35fe.png