尧的笔记

# 5、线性dp &数字三角形

# AcWing 898. 数字三角形

# AcWing 895. 最长上升子序列

# AcWing 896. 最长上升子序列 II

# AcWing 897. 最长公共子序列

# AcWing 902. 最短编辑距离

# AcWing 899. 编辑距离

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }
    int N=510;
    int triangle[][]=new int[N][N];
    int dp[][]=new int[N][N];
    int n;
    int INF= (int) 1e9;
    //n是n个物品
    //m是背包容量
    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                triangle[i][j]= sc.nextInt();
            }
        }
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i],-INF);
        }
        dp[1][1]=triangle[1][1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
            }
        }
        int max=-INF;
        for(int i=1;i<=n;i++){
            if(dp[n][i]>max) max=dp[n][i];
        }
        System.out.println(max);
        //dp
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }
    int N=10010;
    int []nums=new int[N];
    int []dp=new int[N];
    int n;
    void init() {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        for (int i = 0; i < n; i++) {
            nums[i]=sc.nextInt();
        }
        int max= (int) 1;
        Arrays.fill(dp,1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                    if(dp[i]>max) max=dp[i];
                }
            }
        }
        System.out.println(max);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 100010;
    int q[] = new int[N];
    int[] nums = new int[N];
    int n;

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        //二分问题注意自左往右还是自右向左找到第一个值
        //决定是mid+1还是mid-1
        int len = 0;
        for (int i = 0; i < n; i++) {
            int left = 0, right = len;
            while (left < right) {
                int mid = (left + right) / 2;
                if (q[mid] < nums[i]) {
                    left = mid+1;
                } else if (q[mid] >= nums[i]) {
                    right = mid;
                }
            }
            if(left==len) ++len;
            q[left]=nums[i];
        }
        System.out.println(len);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 1010;
    char a[]=new char[N];
    char b[]=new char[N];
    int n,m;
    int f[][]=new int[N][N];

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m=sc.nextInt();
        char as[]= sc.next().toCharArray();
        char bs[]= sc.next().toCharArray();
        for (int i = 0; i < as.length; i++) {
            a[i+1]=as[i];
        }
        for (int i = 0; i < bs.length; i++) {
            b[i+1]=bs[i];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
                if(a[i]==b[j]) f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
            }
        }
        System.out.println(f[n][m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 1010;
    char a[]=new char[N];
    char b[]=new char[N];
    int n,m;
    int f[][]=new int[N][N];

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        char as[]= sc.next().toCharArray();
        m=sc.nextInt();
        char bs[]= sc.next().toCharArray();
        for (int i = 0; i < as.length; i++) {
            a[i+1]=as[i];
        }
        for (int i = 0; i < bs.length; i++) {
            b[i+1]=bs[i];
        }
        for (int i = 0; i <= m; i ++ ) f[0][i] = i;
        for (int i = 0; i <= n; i ++ ) f[i][0] = i;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j]=Math.min(f[i-1][j]+1,f[i][j-1]+1);
                if(a[i]!=b[j]) f[i][j]=Math.min(f[i][j],f[i-1][j-1]+1);
                else f[i][j]=Math.min(f[i][j],f[i-1][j-1]);
            }
        }
        System.out.println(f[n][m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 1010;
    char a[] = new char[N];
    char b[] = new char[N];
    int n, m;
    int f[][] = new int[N][N];

    String strs[] = new String[N];

    int cntDistance(char as[], char bs[]) {
        int la = as.length, lb = bs.length;
        for (int i = 0; i < as.length; i++) {
            a[i + 1] = as[i];
        }
        for (int i = 0; i < bs.length; i++) {
            b[i + 1] = bs[i];
        }
        for (int i = 0; i <= la; i++) f[i][0] = i;
        for (int i = 0; i <= lb; i++) f[0][i] = i;
        for (int i = 1; i <= la; i++) {
            for (int j = 1; j <= lb; j++) {
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (a[i] != b[j]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
                else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
            }
        }
        return f[la][lb];
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i++) {
            strs[i] = sc.next();
        }

        for (int i = 0; i < m; i++) {
            String test=sc.next();
            int limit=sc.nextInt();
            int res=0;
            for (int j = 0; j < n; j++) {
                if(cntDistance(test.toCharArray(),strs[j].toCharArray())<=limit){
                    res++;
                }
            }
            System.out.println(res);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

← 5、背包问题 &01背包、完全背包 →