32 KiB
32 KiB
蓝桥基础
离散化
package LQ_10;
import java.util.*;
public class EXE {
public static void main(String[] args) {
Scanner scan=new Scanner (System.in);
int n=scan.nextInt();
int[] arr=new int[n];
int[] a=new int[n];
for(int i=0;i<n;i++) {
arr[i]=scan.nextInt();
a[i]=arr[i];
}
Set<Integer>set=new HashSet<>();
Arrays.sort(a);
Map<Integer,Integer>map=new HashMap<>();
for(int i=0;i<n;i++)
{
set.add(a[i]);
map.put(a[i],set.size());
}
for(int i=0;i<n;i++)
{
System.out.println(map.get(arr[i])+" ");
}
}
}
进制转化
奇怪的捐赠
地产大亨 Q 先生临终的遗愿是：拿出 100100 万元给 X 社区的居民抽奖，以稍慰藉心中愧疚。
麻烦的是，他有个很奇怪的要求：
- 100 万元必须被正好分成若干份（不能剩余）。每份必须是 7 的若干次方元。比如：1 元, 7 元， 49 元，343 元，...
- 相同金额的份数不能超过 5 份。————》woc 这tm是迷惑你的
- 在满足上述要求的情况下，分成的份数越多越好！
请你帮忙计算一下，最多可以分为多少份？
思路就是：分成多少分，重点是7的平方
想一下一个数是又一个数的各种平方合成的————》进制***太深了
那么难点就是进制转换的问题了
public class Main {
public static void main(String[] args) {
int n=1000000;
int cnt=0;
while(n>0){
cnt+=n%7;
n/=7;
}
System.out.println(cnt);
}
}
常识题
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝的IP地址为 192.168.*.21，其中 * 是一个数字，请问这个数字最大可能是多少？
高精度
题目描述
计算 A×BA×B 。
输入描述
每一行将包含两个整数 AA 和 BB。备注:每个整数的长度不能超过 1000010000。
输出描述
输出 A×BA×B 。
输入输出样例
示例 1
题目描述
计算 A×BA×B 。
输入描述
每一行将包含两个整数 AA 和 BB。备注:每个整数的长度不能超过 1000010000。
输出描述
输出 A×B
1000
2
2000
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.math.BigInteger;***注意导包
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
BigInteger a=scan.nextBigInteger();
BigInteger b=scan.nextBigInteger();
System.out.println(a.multiply(b));
}
}
}
============================================================================================================================================================================================================================================================================================================================
双指针
1372
package LQ_10;
import java.util.*;
public class LQ1372 {
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();//n个数
int s=scan.nextInt();//s 目标常数
int ans=Integer.MAX_VALUE;//表示长度
int sum=0;//表示和
int [] arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=scan.nextInt();
for(int i=0,j=0;i<n;) {
if(sum<s) {
sum+=arr[i];
i++;
}else {
ans=Math.min(i-j,ans);
sum-=arr[j];
j++;
}
}
if(ans==Integer.MAX_VALUE)
System.out.println("0");
else
System.out.println(ans);
scan.close();
}
}
题目核心：
你什么时候达到S以及到达S的时候怎么能最小
刚开始 i=j=0
这个题用的是双指针 就是让sum=0 如果sum<=（都对）s那么就让sum+arr[i],i++ 这样就是扩大了i的长度
既然有扩大长度 那么就有缩短长度 那么如何缩短长度 就是需要j 如果sum>=s 那么就是sum=-arr[j] j++这样 i在前面扩大长度 j在后面缩小长度 当i<n的时候就是到头了 不能扩大了 就是程序结束的时候
Q：你怎么确定 排序是从小打大 （题目似乎没有给出） 是否需要用贪心算法 +动归
============================================================================================================================================================================================================================================================================================================================
常用函数
public static int gcd (int m,int n) {
int r=n;
while(m%n!=0)
{
r=m%n;
m=n;
n=r;
}
return r;
}
R为最小公因数
m*n/r为最小公倍数s
判断是否是素数
public static boolean isPrime (int x) {
if(x==1)
return false;
for(int i=2;i<=Math.sqrt(x);i++)
{
if(x%i==0)
return false;
}
return true;
}
============================================================================================================================================================================================================================================================================================================================
字符串
给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见实例 2）。
package LQ_10;
import java.util.*;
public class LQ396 {
public static void main(String args[]) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int b=Math.abs(n);
StringBuilder str=new StringBuilder();
str.append(b);
StringBuilder str1=str.reverse();
String str2=str1.toString();
int a=Integer.valueOf(str2);
if(n>=0){
System.out.println(a);
}
else{
System.out.println(-a);
}
}
}
排序
冒泡
把最大的冒泡到前面去
int []arr= {5,8,4,4,6,7,4,8};
for (int i = arr.length - 1; i > 0; i--) {
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 与 arr[j + 1]
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
for(int i:arr) {
System.out.printf(i+" ");
}
时间复杂度O N^2
选择
选择最小的与前面的交换
int []arr= {3,8,4,4,6,7,4,8,9,1,1,1,5,2,7,8,15};
for(int i=0;i<arr.length;i++) {
int k=i;
for(int j=i+1;j<arr.length;j++) {
if(arr[j]<arr[k])
k=j;
}
if(k!=i) {
int t=arr[i];
arr[i]=arr[k];
arr[k]=t;
}
}
插入排序
package LQ_10;
public class EXE {
public static void main (String [] args) {
int []nums= {3,8,4,4,6,7,4,8,9,1,1,1,5,2,7,8,15};
for(int i=1;i<nums.length;i++){
int base=nums[i],j=i;
while(j>0&&nums[j]>base) {
nums[j+1]=nums[j];
j--;
}
nums[j+1]=base;
}
for(int i:nums) {
System.out.printf(i+" ");
}
}
}
快排
package LQ_10;
public class EXE {
public static void main(String[] args) {
int[] nums = { 3, 8, 4, 4, 6, 7, 4, 8, 9, 1, 1, 1, 5, 2, 7, 8, 15 };
quickSort(nums,0,nums.length-1);
for (int i : nums) {
System.out.printf(i + " ");
}
}
public static void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
public static void quickSort(int []nums,int left,int right) {
if(left>right)return;//左边的数等于右边的数 就是说只有一个数了 那还排什么
int pivot=partition(nums,left,right);//找中枢点
quickSort(nums,left,pivot-1);
quickSort(nums,pivot+1,right);
}
public static int partition(int []nums,int left,int right) {
int i=left,j=right;
while(i<j) {
while(i<j&&nums[j]>=nums[left])j--;
while(i<j&&nums[i]<=nums[left])i++;
swap(nums,i,j);
}
swap(nums,i,left);
return i;
}
}
归并排序
package LQ_10;
public class EXE {
public static void main(String[] args) {
int[] nums = { 3, 8, 4, 4, 6, 7, 4, 8, 9, 1, 1, 1, 5, 2, 7, 8, 15 };
int[] arr=mergeSort(nums,0,nums.length-1);
for (int i : arr) {
System.out.printf(i + " ");
}
}
public static int[] mergeSort(int[] nums, int left, int right) {
if (left == right)
return new int[] {nums[left]};
int mid = (left + right) / 2;
int[] leftarr = mergeSort(nums, left, mid );
int[] rightarr = mergeSort(nums, mid+1, right);
int[] newarr = new int[leftarr.length + rightarr.length];
int m = 0, l = 0, r = 0;
while (l < leftarr.length && r < rightarr.length)
newarr[m++] = leftarr[l] <rightarr[r] ? leftarr[l++] : rightarr[r++];
while (l < leftarr.length)
newarr[m++] = leftarr[l++];
while (r < rightarr.length)
newarr[m++] = rightarr[r++];
return newarr;
}
}
进制转化
public static String ts(int a,int x) {
StringBuilder str1=new StringBuilder();
while(a>0)
{
str1.append(a%x);
a/=x;
}
return str1.reverse().toString();
}
贪心
package LQ_10;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
List<Integer> lt=new ArrayList<Integer>();
for(int i=0;i<n;i++)
lt.add(scan.nextInt());
long sum=0;
Collections.sort(lt);
while(lt.size()>1) {
int a=lt.get(0);
int b=lt.get(1);
sum+=a+b;
lt.remove(0);
lt.remove(0);
lt.add(a+b);
Collections.sort(lt);
}
System.out.print(sum);
scan.close();
}
}
系统学习
循环
进制转换
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a=scan.nextInt();
int out=0;
int pow=1;
while(a>0){
int c=a%10;
a/=10;
out+=c*pow;
pow*=9;
}
System.out.println(out);
scan.close();
}
}
枚举法求最大公约数
设a, b是两个整数，如果d能整除a且d能整除b，那么，d就称为是a和b的公约数。a和b的公约数中最大的整数称为a和b的最大公约数。
输入两个正整数a和b，求它们的最大公约数。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a = scan.nextInt(), b = scan.nextInt();
int min= Math.min(a, b);
for(int i=min;i>=1;i--){
if(a%i==0 && b%i==0){
System.out.println(i);
break;
}
}
scan.close();
}
}
递归大法
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
sc.close();
System.out.println(gcd(a,b));
}
public static int gcd(int a,int b) {
return b == 0 ? a : gcd(b,a%b);
}
}
数组与字符串
冒泡排序
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=scan.nextInt();
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){//n-1-i n-1是因为有j+1的存在 i是因为每次冒出去一个就会占一个
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for(int i=0;i<n;i++){
if(i==0){
System.out.print(arr[i]);
}
else{
System.out.print(" "+arr[i]);
}
}
scan.close();
}
}
选择排序
/* 选择排序 */
void selectionSort(int[] nums) {
int n = nums.length;
// 外循环：未排序区间为 [i, n-1]
for (int i = 0; i < n - 1; i++) {
// 内循环：找到未排序区间内的最小元素
int k = i;
for (int j = i + 1; j < n; j++) {//因为是找最小的 所以不用从自己开始
if (nums[j] < nums[k])
k = j; // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
JAVA基本API
Integer.parseInt(String s ,int radix) 将（radix表示的s是几进制的）转换为10进制
toString(String s ,int radix) 将s转换为radix进制的字符串
JAVA快读
static FastReader in = new FastReader(); // 创建一个静态的 FastReader 对象，用于处理输入
static PrintWriter out = new PrintWriter(System.out); // 创建一个静态的 PrintWriter 对象，用于输出数据
// FastReader 类，用于处理高效的输入
static class FastReader {
static BufferedReader br; // 静态的 BufferedReader，用于高效读取输入
static StringTokenizer st; // 静态的 StringTokenizer，用于将输入字符串分割为标记
// 构造函数，初始化 BufferedReader 以从标准输入读取数据
FastReader() {
br = new BufferedReader(new InputStreamReader(System.in)); // 使用 System.in 作为输入流初始化 BufferedReader
}
// next() 方法，返回下一个字符串标记
String next() {
String str = ""; // 定义一个空字符串，用于存储读取到的行
// 如果 StringTokenizer 为 null 或没有更多标记可读取，读取新行
while (st == null || !st.hasMoreElements()) {
try {
str = br.readLine(); // 使用 BufferedReader 读取一整行输入
} catch (IOException e) { // 捕获可能的 I/O 异常
throw new RuntimeException(e); // 如果发生异常，抛出运行时异常
}
st = new StringTokenizer(str); // 将读取到的行传递给 StringTokenizer 进行分割
}
return st.nextToken(); // 返回 StringTokenizer 的下一个标记
}
String nextLine(){
String str="";
try {
str = br.readLine(); // 使用 BufferedReader 读取一整行输入
} catch (IOException e) { // 捕获可能的 I/O 异常
throw new RuntimeException(e); // 如果发生异常，抛出运行时异常
}
return str;
}
// nextInt() 方法，返回下一个整数输入
int nextInt() {
return Integer.parseInt(next()); // 使用 next() 方法读取字符串并转换为整数
}
// nextDouble() 方法，返回下一个双精度浮点数输入
double nextDouble() {
return Double.parseDouble(next()); // 使用 next() 方法读取字符串并转换为双精度浮点数
}
// nextLong() 方法，返回下一个长整数输入
long nextLong() {
return Long.parseLong(next()); // 使用 next() 方法读取字符串并转换为长整数
}
}
还有一种
class Read{
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public int nextInt() throws Exception{
st.nextToken();
return (int)st.nval;
}
public String readLine() throws Exception{ // 不推荐使用
st.nextToken();
return st.sval;
}
}
一维前缀和
本题为一维前缀和模板。
给定一个长度为 n 的序列 a。
再给定 q组查询，对于每次查询:给定一对l r,你需要输出 的结果。
输入格式
第一行输入两个正整数 n, q。(1 ≤ n,q < 10°)
第二行输入 n 个正整数 αi。(1 ≤i≤ n,1 ≤ ai< 104)。
接下来 q 行，每行输入 2 个正整数 l,γ。(1 <l<r< n)。
输出格式
对于每次查询，输出一行一个整数，表示该次查询的结果。
样例输入
5 3
2 1 3 6 4
1 2
1 3
2 4
输出
3
6
10
自制小代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt(),q=scan.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=scan.nextInt();
}
for(int i=0;i<q;i++){
int l=scan.nextInt(),r=scan.nextInt();
int sum=0;
for(int j=l-1;j<r;j++){
sum+=arr[j];
}
System.out.println(sum);
}
scan.close();
}
} 简单易懂 但是时间很长
标准答案 利用了求和公式的变形
S[n]=s[n-1]+a;
然后要求l到r的和就是 S[r]-s[l-1] 因为是包括L的所以说是从L-1开始的
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt(),q=scan.nextInt();
int arr[]=new int[n+2];
arr[0]=0;
for(int i=1;i<=n;i++){
arr[i]=scan.nextInt()+arr[i-1];
}
for(int i=0;i<q;i++){
int l=scan.nextInt(),r=scan.nextInt();
System.out.println(arr[r]-arr[l-1]);
}
scan.close();
}
}
差分
问题描述
给定一个长度为 n 的序列 a。
再给定 m 组操作，每次操作给定3个正整数l,",d，表示对 ai~，中的所有数增加 d。
最终输出操作结束后的序列 a。
Update:由于评测机过快，n,m于2024-12-09 从 105加强至 2 x105杜绝暴力通过本题。
输入格式第一行输入两个正整数n,m。(1<n,m<2x105)第二行输入 n 个正整数 ai。(1 ≤i≤ n,1 ≤ ai < 104)。接下来 m 行，每行输入 3 个正整数 l,™,d。(1 ≤l≤r≤ n,-104 ≤d≤ 104)。
输出格式
输出 几 个整数，表示操作结束后的序列 a。
样例输入
6 3
2 2 12 1
3 1
5
6 1
样例输出
3 4 5 3 4 2
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n= scan.nextInt(), m=scan.nextInt();
int arr[]=new int[n+5];
int brr[]=new int[n+5];
int crr[]=new int[n+5];
arr[0]=0;brr[0]=0;crr[0]=0;
for(int i=1;i<=n;i++) arr[i]=scan.nextInt();
for(int i=1;i<=n;i++) brr[i]=arr[i]-arr[i-1];
for(int i=1;i<=m;i++){
int l=scan.nextInt(),r=scan.nextInt(),d=scan.nextInt();
brr[l]+=d;
brr[r+1]-=d;
}
for(int i=1;i<=n;i++) crr[i]=crr[i-1]+brr[i];
for(int i=1;i<=n;i++){
System.out.print(crr[i]+" ");
}
scan.close();
}
}
差分数组求前缀和就是求原数组
小蓝的操作（2星）
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();//n家店铺
int t = in.nextInt();//t行点赞情况
int q = in.nextInt();//q组查询
int x = in.nextInt();//信赖店铺的点赞数量
int arr[] = new int[n+20];//开辟一个n个空间的数组 表示店铺
for (int i = 0; i < t; i++) {
int l = in.nextInt();
int r = in.nextInt();
arr[l] += 1;//我在l的地方+1 在我后面代码arr[i]+=arr[i-1]中 所有的在l后面的代码都会加上1
arr[r+1] -= 1;//但是我又为了防止 r后面的不能加上因为我的加的范围是l-r 所以 r+1就需要减去1 与前面的l对冲
}
for (int i = 1; i <= n; i++) {
arr[i] = arr[i] + arr[i - 1]; //将差分数组 转化为原数组 bn=an+an-1
}
int brr[]=new int[n+10];
for (int i = 1; i <= n; i++) {
if (arr[i] >= x)//如果被定义为信赖的为1
arr[i]=1;
else
arr[i]=0;
brr[i]=brr[i-1]+arr[i];//前缀和
}
for(int i=1;i<=q;i++){
int l= in.nextInt(),r= in.nextInt();
System.out.println(brr[r]-brr[l-1]);
}
in.close();
}
}
二维差分数
给定一个 大小的矩阵 。 给定 组查询，每次查询为给定 4 个正整数 ，你需要输出 的值。
第一行输入 3 个正整数 。 接下来 行每行输入 个整数，表示 。 接下来 行，每行输入 4 个正整数
对于每次查询，输出一个整数，表示查询的子矩阵的和。
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
样例输出
17
27
21
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int q = scan.nextInt();
int[][] sum = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + scan.nextInt();
}
}
while (q-- > 0) {
int x1 = scan.nextInt();
int y1 = scan.nextInt();
int x2 = scan.nextInt();
int y2 = scan.nextInt();
int result = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
System.out.println(result);
}
scan.close();
}
}
单调队列
滑动窗口问题
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] num = new int[10];
int n, k;
n = sc.nextInt();
k = sc.nextInt();
int[] ans = new int[n - k + 1];
Deque<Integer> q = new ArrayDeque();
for (int i = 0; i < n; i++) {
while (!q.isEmpty() && num[i] > num[q.peekLast()]) {
q.pollLast();
}
q.addLast(i);
if (i - q.getFirst() >= k) {//如果队列头部的元素已经不在滑动窗口内，则将其移除
q.pollFirst();
}
if (i >= k - 1)
ans[i - k + 1] = num[q.getFirst()];//记录当前滑动窗口的最大值
}
}
}
位运算
相或为k（2星）
问题描述
给定你n个非负整数a[i]，你是否可以从中选出一些数进行或运算使得值为k，若可以，则输出Yes，若不可以，则输出No。
或运算：二进制位1|1 = 1, 1|0 = 1, 0|0 = 0。
输入格式
第一行一个t代表数据组数。
每组数组第一行二个整数n, k。
每组数据第二行n个数a[i]。
输出格式
输出t行，为符合题目要求的Yes或No。
样例输入
1
4 6 1 2 3 4
样例输出
Yes
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0) {
int n = sc.nextInt();
int k= sc.nextInt();
int ans=0;
for(int i=0;i<n;i++){
int r= sc.nextInt();
if((r&k)==r){
ans|=r;
}
}
/**
* 判断是否为k的子集
* 如果r&k==r，则说明r是k的子集
* 就让ans 加上r也就是ans|r
* 最后再看是否ans==k 也就是所有的k的子集是否都出现了
* 这个题 题目不好理解 但是 只要理解了 就很简单了
*/
if(ans==k){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
}
求阶乘（3星）
问题描述：满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少？如果这样的 N 不存在输出 -1 。 输入格式：一个整数 K 。 输出格式：一个整数代表答案。
样例输入： 2
样例输出： 10
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static long cale(long x) {
long num = 0;
while (x > 0) {
//求出能有几个会被5整除的 因为在阶乘中5有1个5 25有2个5 所以说通过循环 来判断这个数究竟能被几个5整除
num += x / 5;
x /= 5;
}
return num;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long n = scan.nextLong();
long left = 0L;
long right = (long) 1e18 ;
while (left < right) {
long mid = (left + right) / 2;
if(n<=cale(mid)){
right = mid ;
}
else{
left = mid+1 ;
}
}
if(cale(right)!=n){
System.out.println(-1);
}
else{
System.out.println(right);
}
scan.close();
}
}
莫名其妙中间省略了好多
背包01dp
n = in.nextInt();
m = in.nextInt();
int []v=new int[n+1];//价值
int []w=new int[n+1];//体积
for(int i=0;i<n;i++){
v[i]=in.nextInt();
w[i]=in.nextInt();
}
int [][]dp=new int[m+1][m+1];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}
//////////////////////////////// ////////////////////////////////////////////////////////////////
一维优化
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n, m;
n = in.nextInt();
m = in.nextInt();
int[] v = new int[n + 1];
int[] w = new int[n + 1];
for (int i = 0; i < n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
int[] dp = new int[m + 1];
for (int i = 0; i < n; i++) {
for (int j = m; j >= w[i]; j--) {//这是从后往前来的 只能这样 因为只有这样 不然从前往后的话就会多加
dp[j] = Math.max(dp[j], dp[ j - w[i] ] + v[i]);
/*
是这样的 因为啊 这个dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
需要等价于
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
dp[j] = Math.max(dp[j] 是没有错的Math.max(dp[j] 是上一个的 其实就是等价于dp[i][j]=Math.max(dp[i][j]
可以这么认为 因为此时左边的dp[j]还没有被算出来 而右边的dp[j]是上一个dp[i-1][j]的 已经被算出来的
*/
}
}
in.close();
}
}
完全背包
n = in.nextInt();
m = in.nextInt();
int []v=new int[n+1];//价值
int []w=new int[n+1];//体积
for(int i=0;i<n;i++){
v[i]=in.nextInt();
w[i]=in.nextInt();
}
int [][]dp=new int[m+1][m+1];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
}
//注意这个 dp[i][j]=Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
其实完全背包和01背包差不多 都是依赖上一层的来推出下一层
只不过完全背包可以对同一个物品多次拿去 所以它的上一层就可能是自己发展过来的 所以就是dp[i][j-w[i]]+v[i]
////////////////////////////////////////////////////////////////////////////////////////////////
一维优化
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n, m;
n = in.nextInt();
m = in.nextInt();
int[] v = new int[n + 1];
int[] w = new int[n + 1];
for (int i = 0; i < n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
int[] dp = new int[m + 1];
for (int i = 0; i < n; i++) {
for (int j =w[i]; j<=m; j++) {//这是从前往后来的 所以说就是可以直接从w[i]到m 跟上面的反着记就好了
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
in.close();
}
}
多重背包
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt();
int v[]=new int[n+1];
int w[]=new int[n+1];
int c[]=new int[n+1];
int dp[]=new int[m+1];
for (int i = 1; i <= n; i++) {
v[i]=sc.nextInt();
w[i]=sc.nextInt();
c[i]= sc.nextInt();
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >=v[i]; j--) {
for (int k = 0; k*v[i]<=j&&k<=c[i] ; k++) {//不仅选的次数要关注容量 也要关注本身的限制
dp[j]=Math.max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
}
System.out.println(dp[m]);
}
}
O(N*M*K)比较大 只能支持100的数值
区间DP
题目描述
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。例如：输入{1，2，3，4，5}，输出33。【3+6+9+15=33】
输入
本题应该处理到文件尾，每组输入包括两行，第一行为石子堆的个数n，第二行则为每堆石子的个数。
输出
输出最小花费。
样例输入
5
1 2 3 4 5
样例输出
33
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int N = 300;
static int[] s = new int[N];//前缀和
static int[][] dp = new int[N][N];//i j 这个数组的每一位ij 都代表的是i->j 的最少的花费
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt();
for(int i=1;i<=n;i++){
s[i]=in.nextInt()+s[i-1];
}
for(int len=2;len<=n;len++){
for(int l=1;len+l-1<=n;l++){
int r =len+l-1;
dp[l][r]=Integer.MAX_VALUE;
for(int k = l; k< r; k++){
dp[l][r]=Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
}
}
}
System.out.println(dp[1][n]);
}
}