头像

封锁线




在线 


最近来访(11)
用户头像
hihihi
用户头像
DGJG
用户头像
fifty-three
用户头像
瞳孔里的天
用户头像
tonngw

活动打卡代码 AcWing 1. A + B

封锁线
1分钟前
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        System.out.print(A+B);
    }
}


活动打卡代码 AcWing 282. 石子合并

封锁线
23小时前
import java.util.*;
class Main{
    /*
    状态表示 f[i,j]
        集合 所有将第i堆石子到第j堆石子合并到一堆石子的合并方式
        属性 这些合并方式中代价最小的方式
    状态计算 划分集合
             i与(i+1,j), (i,i+1)与(i+2,j),(i,i+2)与(i+3,j),...,(i,j-1)与(j)
             或者  k = j-i+1
             1与k-1,2与k-2,...,k-1与1

             举例 : 左边 [i,k], 右边 [k+1,j]
             那么 f[i,j] = f[i,k] + f[k+1,j] + s[j] - s[i-1] (s:前缀和)
    */
    static int N = 310;
    static int[][] f = new int[N][N];
    static int[] stack = new int[N]; 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++){
            stack[i] = sc.nextInt();

        }

        for(int i=1;i<=n;i++){
            stack[i] += stack[i-1]; // 前缀和
        }

        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1 <=n;i++){
                int l = i;
                int r = len + i-1;
                f[l][r] = 100000000;
                for(int k=l;k<r;k++){
                    f[l][r] = Math.min(f[l][r],f[l][k] + f[k+1][r] + stack[r] - stack[l-1]);
                }
            }
        }

        System.out.print(f[1][n]);



    }


}



import java.io.*;
//给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
class Main{
    // 状态表示:f[i][j] : N中[1,i]的子串与M中[1,j]的子串中的最长公共子序列 (索引从1开始)
    // 集合: N中[1,i]的子串与M中[1,j]的子串中的最长公共子序列
    // 属性: 集合中所有公共子序列的最大长度
    // 状态计算: 划分集合——A[i]和B[j]是否出现在子序列中
    // 四种情况:
    // 1、00 不选A[i]和B[j] :f[i-1][j-1]  
    // 2、01 不选A[i]和选B[j]:f[i-1][j]
    // 3、10 选A[i]和不选B[j] : f[i][j-1]
    // 4、11 选A[i] 和 选 B[j] f[i-1][j-1] + 1
    // A[i] != B[j]: 在划分为用A[i]和不用B[j] 
    // f[i][j] = Math.max(f[i-1][j],f[i][j-1])
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] param = br.readLine().split(" ");
        int n = Integer.parseInt(param[0]);
        int m = Integer.parseInt(param[1]);
        String A = br.readLine();
        String B = br.readLine();
        // System.out.print(A + " " + B);
        int[][] f = new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A.charAt(i-1) == B.charAt(j-1)){
                    f[i][j] = f[i-1][j-1]  + 1;
                }
                else{
                    f[i][j] = Math.max(f[i-1][j],f[i][j-1]);
                }
            }
        }
        System.out.print(f[n][m]);
    }

}



import java.util.*;
class Main{
    static int N = 100010;
    static int[] a = new int[N];
    static int[] q = new int[N]; 
    static int INF = 0x3f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }

        // q[i] : 存放长度为i的上升子序列末尾元素的最小值
        int len = 0;
        q[0] = - INF;
        // 每遇到一个新元素 a[i],通过二分在q中找到比a[i]小的最大值q[k],表示a[i]可以接到长为k的上升子序列后面
        // 
        for(int i=0;i<n;i++){
           int l = 0;
           int r = len; // len:q中最长上升子序列的长度
           while(l < r){
               int mid = l + r + 1>> 1; // 二分: 左区间: < a[i] ;  右区间 :>= a[i],要获得左区间的右边界,+1
               if(q[mid] < a[i]){
                   l = mid;
               }
               else{
                   r = mid - 1;
               }
           }
           // 更新最长子序列长度,因为a[i]能接到q[r]表示的上升子序列后面,因此长度为 r+1
           len = Math.max(len,r+1); 
           q[r+1] = a[i];  // q[r]<a[i]<=q[r+1]
        }

        System.out.print(len);

    }
}



import java.util.*;
class Main{
    static int N = 1010;
    static int[] a = new int[N];
    static int[] f = new int[N]; 
    // 集合: 所有以第i个数结尾的上升子序列
    // 属性: 集合中最长的上升子序列的长度
    // 状态转移: 从集合{f[1],f[2],...,f[i-1]}里找,如果a[i]比a[j](1<=j<=i-1) 大,那么f[i] = Math.max(f[j] + 1,f[i]);
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++){
            a[i] = sc.nextInt();
        }
        for(int i=1;i<=n;i++){
            f[i] = 1;
        }
        int res = 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){ 
                if(a[i] > a[j]) f[i] = Math.max(f[j] + 1,f[i]);
            }

            res = Math.max(res,f[i]);
        }
        System.out.print(res);

    }
}


活动打卡代码 AcWing 898. 数字三角形

import java.util.*;
class Main{
    static int INF = 0X3f3f3f3f;
    static int N = 510;
    static int[][] a = new int[N][N];
    static int[][] f = new int[N][N];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                a[i][j] = sc.nextInt();
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=0;j<=i+1;j++){
                f[i][j] = - INF;
            }
        }
        f[1][1] = a[1][1];
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                f[i][j] = Math.max(f[i-1][j-1] + a[i][j],f[i-1][j]+a[i][j]);
            }
        }
        int max = -INF;
        for(int i=1;i<=n;i++){
            max = Math.max(max,f[n][i]);
        }
        System.out.print(max);
    }
}


活动打卡代码 AcWing 9. 分组背包问题

import java.util.*;
class Main{
    // 状态表示: f[i,j]
    //     集合: 只从前i组物品中选,并且总体积不大于j的所有选法
    //     属性:  集合中所有选法中价值的最大值
    // 状态计算: 集合划分
    // f[i,j] = max(选第i组中的物品,不选第i组中的物品) = max(f[i][j],f[i-1][j])
    // 而 第i组中有k种物品,从中枚举选一种物品,即f[i,j] = f[i-1,j - v[i,k]] + w[i,k]

    static int N = 101;
    static int[][] V = new int[N][N]; // 第i组中第k种
    static int[][] W = new int[N][N];
    static int[] f = new int[N];
    static int[] s = new int[N];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i=1;i<=n;i++){
            s[i] = sc.nextInt();
            for(int j=0;j<s[i];j++){
                V[i][j] = sc.nextInt();
                W[i][j] = sc.nextInt();
            }
        }
        for(int i=1;i<=n;i++){
            for(int j = m;j>=0;j--){
                for(int k=0;k<s[i];k++){
                    if(V[i][k] <= j)
                        f[j]=  Math.max(f[j],f[j-V[i][k]] + W[i][k]);
                }
            }
        }

        System.out.print(f[m]);



    }

}


活动打卡代码 AcWing 5. 多重背包问题 II

每个物品的个数s[i]:拆成1,2,4,8,…,2^k,s[i] - (2^(k+1)-1)
每个包都视为一个新物品

import java.util.*;
class Main{
    // 多重背包优化: 一个物品i能取s[i]次,我们将 s[i] 拆成:1,2,4,8,...,2^k,s[i] - 2^k
    // 每一个分组是一个包,视为一个新的物品
    // 对每一种物品都进行拆分,从而将多重背包问题转换为0-1背包问题。
    // N 开 25000的原因: 因为0<s≤2000,2^11 = 2048,因此当s = 2000时,最多拆成 1,2,4,...,2^9,2000-1023
    // 因此对于s = 2000,最多拆成11个包:2^0 , 2^1 ,...,2^9,2000-1023,因此N要开到11001 (0不存)
    static int N = 11001; 
    static int[] V = new int[N];
    static int[] W = new int[N];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int cnt = 0; // 标记总共拆分了多少个包
        for(int i=1;i<=n;i++){
            int a = sc.nextInt(); // 容量
            int b = sc.nextInt(); // 价值
            int s = sc.nextInt(); // 个数
            int k = 1;
            // 1,2,4,..,8,...,2^k = 2^(k+1) -1
            while(k<s){
                cnt++;
                V[cnt] = k * a;
                W[cnt] = k * b;
                s-= k;
                k *= 2;
            }
            // 剩余部分分为另一类  s - 2^(k+1) -1
            if(s > 0){
                cnt ++;
                V[cnt] = s * a;
                W[cnt] = s * b;
            }

        }
        // 0-1背包优化
        n = cnt;
        int[] f = new int[m+1];
        for(int i=1;i<=n;i++){
            for(int j=m;j>=V[i];j--){
                f[j] = Math.max(f[j],f[j-V[i]] + W[i]);
            }
        }
        System.out.print(f[m]);
    }
}


活动打卡代码 AcWing 4. 多重背包问题

import java.util.*;
class Main{
    /*
    状态表示:f(i,j)
    集合: 所有从前i个物品中选,不超过容量j的所有选法
    属性: 集合中所有选法的最大价值

    状态计算:划分集合为 选第i个物品和不选第i个物品
    不选: f[i-1][j] 
    选: 选1个,2个,...., s[i]个 (第i个物品最多选s[i]个)
    f[i][j] = max(f[i-1][j-k*V[i]) + k * W[i]) ,k=0,1,2,...,s[i]
    */

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] V = new int[n+1];
        int[] W = new int[n+1];
        int[] S = new int[n+1];
        for(int i=1;i<=n;i++){
            V[i] = sc.nextInt();
            W[i] = sc.nextInt();
            S[i] = sc.nextInt();
        }

        // 朴素版本
        int[][] f = new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k<=S[i] && k*V[i] <= j;k++){
                    f[i][j] = Math.max(f[i][j],f[i-1][j-k*V[i]] + k*W[i]);
                }
            }
        }


        System.out.print(f[n][m]);
    }
}


活动打卡代码 AcWing 3. 完全背包问题

优化
屏幕截图 2022-09-27 214021.png
又因为f(i,j) 只和 f(i,j-v[i])相关,因此:
f[j] = Math.max(f[j],f[j-V[i]] + W[i]);

import java.util.*;
class Main{
    static int N = 1010;
    static int[] V = new int[N];
    static int[] W = new int[N];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int v = sc.nextInt();
        for(int i=1;i<=n;i++){
            V[i] = sc.nextInt();
            W[i] = sc.nextInt();
        }

        // 状态表示: f(i,j):从 1-i里面选,最大容量为j时的最大价值
        // f(i,j)集合: 所有只考虑前i个物品,且总体积不大于j的所有选法
        // 属性: 集合中所有选法中总价值的最大值 
        //
        // 状态计算:集合划分
        // f(i,j): 首先划分为 取第i个物品和不取第i个物品
        // 不取第i个物品: f[i-1,j]
        // 取第i个物品: f[i,j],但第i个物品能取无限次,曲线救国,先去掉再加上,即:
        // f(i,j) = Max{f(i-1,j-V[i]) + w[i],f(i-1,j-2*V[i]) + 2*w[i],....,f(i-1,j-k*V[i]) + k*w[i]}
        // 而 f(i-1,j) 为 k=0 的情况,因此 f(i,j) = Max{f(i-1,j-k*V[i]) + k*w[i]}: k=0,1,....n
        // 朴素写法
        // int[][] f = new int[n+1][v + 1];
        // for(int i=1;i<=n;i++){
        //     for(int j=0;j<=v;j++){
        //         for(int k=0;k*V[i] <= j;k++)
        //             f[i][j] = Math.max(f[i][j],f[i-1][j-k*V[i]] + k*W[i]);
        //     }
        // }

        // 优化: 从左往右递推,f[j] = Math.max(f[j],f[j-V[i]] + W[i]);
        int[] f = new int[v + 1];
        for(int i=1;i<=n;i++){
            for(int j=V[i];j<=v;j++){
                f[j] = Math.max(f[j],f[j-V[i]] + W[i]);
            }
        }
        System.out.print(f[v]);
    }
}