大良营销网站建设好么,餐饮公司企业网站源码,西安专业网站排名优化,为什么要做手机网站题目一 啊 看着挺复杂 其实很简单
第一种方法
就是纵轴是怪兽编号 横轴是能力值
看看能不能打过
逻辑很简单 看看能不能打得过 打过的就在花钱和直接打里面取小的 打不过就只能花钱
这种方法就导致 如果怪兽的能力值很大 那么我们就需要很大的空间
所以引出下一种做法
纵…题目一 啊 看着挺复杂 其实很简单
第一种方法
就是纵轴是怪兽编号 横轴是能力值
看看能不能打过
逻辑很简单 看看能不能打得过 打过的就在花钱和直接打里面取小的 打不过就只能花钱
这种方法就导致 如果怪兽的能力值很大 那么我们就需要很大的空间
所以引出下一种做法
纵轴是怪兽编号 横轴是钱数
我们对比一下这两种方法
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块钱能通过j9都不行
然后推到最后一行 从左后一行里面找最左面不为-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.length1][sum1];for(int i 0;id.length;i) {for(int j 0;jsum1;j) {dp[i][j] -1;}}dp[0][p[0]] d[0];//第一行只有这个位置有值for(int i 1;id.length;i) {for(int j 0;jsum1;j) {if(jp[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推了一遍 就是说 当L0 R4 的时候怎么求 如果我aa那就看cbc是怎么变回文的 acb怎么变回文 那就要看ac是怎么变的 cb是怎么变的 在除去开头/结尾的情况下先把它变成回文 然后我们只需要考虑这不是回文的一个字符(就是加上)就可以了
我之前比较困惑的是bab 如果 我在做ba的时候 我直接在后面加了一个b 那我还要也就是变成了bab 已经是回文了 那我这个原本的b怎么处理呢?
如果是bab 在推ba的时候 我们或许会在前面加a 或许会在后面补b 但是如果ba了 那我们就要看a是怎么变回文串的 而不是ba怎么变的 第三题
一种消息接收并打印的结构设计已知一个消息流会不断地吐出整数1~N,但不一定按照顺序吐出。如果上次打印的数为i那么当i1出现时请打印i1及其之后接收过的并且连续的所有数直到1~N全部接收并打印完请设计这种接收并打印的结构。初始时默认i0
多个空间
比如最开始我们加入 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 HashMapInteger, Node headMap;private HashMapInteger, Node tailMap;private int waitPoint;public Messagebox() {headMap new HashMapInteger, Node();tailMap new HashMapInteger, 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);}// 查询有没有某个连续区间以num1开头的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();}
}
