头像

CoderXx


访客:1478

离线:19小时前



CoderXx
1天前

题目描述

给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串长度最长是多少。

输入格式
第一行包含两个整数N和M。

第二行包含一个长度为N的字符串,表示字符串A。

第三行包含一个长度为M的字符串,表示字符串B。

字符串均由小写字母构成。

输出格式
输出一个整数,表示最大长度。

数据范围
1≤N,M≤1000

样例

输入样例:

4 5
acbd
abedc

输出样例:

3

算法

DP $O(n^2)$

谈一下自己的理解:
f[i][j]是字符串q的前i个字符和字符串p的前j个字符中公共子序列的最大值。
计算f[i][j]的时候将其划分为4种情况:q[i]p[i]都不取,q[i]取p[j]不取,q[i]不取p[i]取,q[i]p[i]都取。
都取的情况q[i]==p[i],q[i]p[i]都不取对应f[i-1][j-1]
剩下两种情况用f[][]形式不好表示但是其被包含在f[i-1][j]和f[i][j-1]中。
这两种状态包含的情况是大于上述情况的且存在并集,但是取值为最大值不影响。

时间复杂度

Java 代码

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();int m = sc.nextInt();
        String p = " " + sc.next(), q = " " + sc.next();
        int[][] f = new int[n + 1][m + 1];

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
                if(p.charAt(i) == q.charAt(j)) f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
            }
        }
        System.out.println(f[n][m]);
    }
}



CoderXx
1天前
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();int m = sc.nextInt();
        String p = " " + sc.next(), q = " " + sc.next();
        int[][] f = new int[n + 1][m + 1];

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
                if(p.charAt(i) == q.charAt(j)) f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
            }
        }
        System.out.println(f[n][m]);
    }
}


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

CoderXx
1天前
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] s = new int[n+1];
        int[][] f = new int[n+1][n+1];
        for(int i = 1; i <= n; i++){
            s[i] = sc.nextInt();//s存储的是前缀和
            s[i] += s[i-1];
        }

        for(int len = 2; len <= n; len++){//划出区间
            for(int i = 1; i + len - 1 <= n; i++){
                int l = i, r = i + len - 1;
                f[l][r] = 10000000;
                for(int k = l ; k < r; k++){
                    f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l-1]);
                }
            }
        }
        System.out.println(f[1][n]);
    }
}



CoderXx
1天前
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();int m = sc.nextInt();
        String p = " " + sc.next(), q = " " + sc.next();
        int[][] f = new int[n + 1][m + 1];

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
                if(p.charAt(i) == q.charAt(j)) f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
            }
        }
        System.out.println(f[n][m]);
    }
}



CoderXx
2天前
import java.util.*;
public class Main{

    public static void main(String[] args){
        //f[i]表示以a[i]结尾的最长上升子序列。
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1], f = new int[n+1];
        for(int i = 1; i <= n; i++)
            a[i] = sc.nextInt();

        for(int i = 1; i <= n; i++){
            f[i] = 1;//若a[i]结尾的递增子序列都没有,前面的数字都比a[i]大那么f[i]等于1,a[i]以自己为结尾.
            for(int j = 1; j < i; j++){
                if(a[j] < a[i]){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int res = 0;
        for(int i = 0; i <= n; i++) res = Math.max(res, f[i]);//求完f[i]后在f[i]中寻找一个最大值。

        System.out.println(res);
    }
}


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

CoderXx
3天前
//这里填你的代码^^
import java.util.*;
public class Main{

    private static final int N = 510;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[N][N], f = new int[N][N];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                nums[i][j] = sc.nextInt();
            }
        }

        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= i + 1; j++){
                f[i][j] = Integer.MIN_VALUE;
            }
        }

        f[1][1] = nums[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], f[i-1][j] )+ nums[i][j];

        int res = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) res = Math.max(res, f[n][i]);
        System.out.println(res);
    }
}


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

CoderXx
3天前
import java.util.*;

class Main{

    private static final int N = 110;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] v = new int[N][N], w = new int [N][N];
        int[] s = new int[N], f = new int[N];

        for(int i = 1; i <= n; i++){
            s[i] = sc.nextInt();
            for(int j = 1; 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 = 1; k <= s[i]; k++){
                   if(j >= v[i][k])f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]); 
               }
           }
        }

        System.out.println(f[m]);
    }

}


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

CoderXx
3天前
import java.util.*;
public class Main {

    private static final int N = 25000;

    public static void main(String[] args) {
        System.out.println(multiplePacketProblems());
    }

    private static int multiplePacketProblems(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[N], w = new int[N];
        int[] f = new int[N];
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), s = sc.nextInt(), k = 1;
            while( k <= s){
                cnt++;
                v[cnt] = a * k;
                w[cnt] = b * k;
                s -= k;
                k *= 2;
            }
            if(s > 0){
                cnt++; 
                v[cnt] = a * s;
                w[cnt] = b * s;
            }
        }


        for(int i = 1; i <= cnt; i++)
            for(int j = m; j >= v[i]; j--)
                f[j] = Math.max(f[j], f[j-v[i]] + w[i]);

        return f[m];
    }
}


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

CoderXx
4天前
import java.util.*;
public class Main {

    public static void main(String[] args) {
        System.out.println(multiplePacketProblems());
    }

    private static int multiplePacketProblems(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[n+1], w = new int[n+1], s = new int[n+1];
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }

        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 ++){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-k*v[i]] + k * w[i]);
                }
            }
        }
        return dp[n][m];
    }
}


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

CoderXx
4天前
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        System.out.println(completePacketProblem());
    }

    private static int completePacketProblem(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[n+1], w = new int[n+1];
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for(int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= v[i]) dp[i][j] = Math.max(dp[i][j], dp[i][j-v[i]] + w[i]);
            }
        }
        return dp[n][m];
    }
}