目录

牛客.小红取数

 牛客.哈夫曼编码​编辑

牛客.字符编码(上一道题的资料)

牛客.最小的完全平方数

---

牛客.小红取数

01背包问题:在满足总和必须为k的倍数的情况下，选择最大的总和

1.状态表示:

dp[i][j]:表示从前面i个数字中挑选，总和%k等于j时候,最大的和是多少

因为这个同余定理

2.状态转移方程

不选dp[i-1][j];

选择的话就是

dp[i][j]=dp[i-1][j-a[i]%k]+a[i];

但是j-a[i]%k又可能为负数，此时修正就再加上k即可，但是加k,又会面对超的问题

(j-a[i]%k+k)%k

从前面为0的数字，我都没有数字，啥都选不到，那么余数就是0，但是其他是非法的，所以不能让他选择这里面的值进行参考。

这块的调试，做个参考，用的例子就是测试用例。我们可以看到，最开始第一个数字的余数只能有一个数字是4，结果没想到全变成4了，这也就是说，这个用了上面的0处非法值，所以才要初始化。

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();long[]a=new long[n+1];for(int i=1;i<=n;i++){a[i]=in.nextLong();}long[][]dp=new long[n+1][k];//余数只有可能[0-k-1]for(int i=0;i<=n;i++){for(int j=0;j<k;j++){
//一定要初始化一个足够大的数字
//因为我们这个并不知道他会去上一层找哪一个，所以我们需要初始化负无穷，让他不去考虑这些事情dp[i][j]=-0x3f3f3f3f3f3f3f3fL;}}
//前面0个数字里面挑选dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<k;j++){   dp[i][j]=Math.max(dp[i-1][(int)(j-a[i]%k+k)%k]+a[i],dp[i-1][j]);}}if(dp[n][0]>0){System.out.print(dp[n][0]);}else{System.out.print(-1);}} 
}

 牛客.哈夫曼编码

刚开始压缩存储，找到里面每个字符存的次数，然后根据次数编辑01字符串，但是假如出现用某序列表示某个字符，但是面临的问题就是，序列中有的是可拆分的，比如说

world 可以拆分 w orld ,wo rld 这种等等

输出最后带权路径长度

边构建，一边统计

比如我们会用到下面的一个1，一个2

1+2，还会用到上面着两个三，也就是1+2+3+3即可。小根堆，弹出两个，然后相加，放里面一个。

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();PriorityQueue<Long>q=new PriorityQueue<>();         long sum=0;for(int i=0;i<n;i++){q.add(in.nextLong());}//构建最优二叉树,最后的那一层不去算，因为最后添加的是6while(q.size()>1){long t1=q.poll();long t2=q.poll();q.add(t1+t2);sum+=t1+t2;}System.out.print(sum);}
}

牛客.字符编码(上一道题的资料)

M:2

T:3

-:2

E:2

C:1

H1

A:1

先从小的开始依次连接

问题是一样的

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNext()){int []hash=new int[300];PriorityQueue<Integer>q=new PriorityQueue<>();char[]s=in.next().toCharArray();for(int i=0;i<s.length;i++){
//这道题的哈希表就别-A，啥的了，他的字符不一定都是啥，但是哈希表做到全统计了就好hash[s[i]]++;}for(int i=0;i<300;i++){if(hash[i]!=0){q.add(hash[i]);}}int sum=0;while(q.size()>1){int a=q.poll();int b=q.poll();q.add(a+b);sum+=a+b;}System.out.println(sum);}}
}

牛客.最小的完全平方数

 

很是玄妙的思想，需要好好啃食，最好用两个例子，一测试就明白了

初始化dp[0][0]=0,其余为无效的值。

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();//从前i个数字中挑选，总和恰好为j时候，最少的跳出来的个数int[][]dp = new int[n][n + 1];for (int j = 0; j <= n; j++) {dp[0][j] = 0x3f3f3f3f;}dp[0][0] = 0;for (int i = 1; i <= Math.sqrt(n); i++) {for (int j = 1; j <= n; j++) {dp[i][j] = dp[i - 1][j];if (j - i * i >= 0) {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - i * i] + 1);}}}System.out.print(dp[(int)Math.sqrt(n)][n]);}
}