头像

鼠鼠我

山东科技大学




离线:1天前


最近来访(16)
用户头像
菜菜我最菜
用户头像
Amaryllis_
用户头像
问题儿童
用户头像
锦木千束
用户头像
yxc的小迷妹
用户头像
lorenzo_必上岸
用户头像
ekatsim
用户头像
y_yy
用户头像
梦里_0
用户头像
小孩39
用户头像
窗外的麻雀
用户头像
昼酒
用户头像
Kirito_
用户头像
啥时候能学会
用户头像
0000sz
用户头像
从前


题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 310;
    static int[] a = new int[N];
    static int[][] f = new int[N][N];//f[i][j]表示将所有[i-j]合并成一堆的方案集合,取最小值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(s[i-1]);
            a[i] += a[i-1];//区间和
        }
        //套路:先枚举区间长度
        for (int len = 2; len <= n; len++) {//从2开始
            for (int i = 1; i + len -1 <= n; i++) {//枚举左区间,减一是左区间最多到n-1,然后右区间留一个
                int j = i + len -1;
                f[i][j] = (int) 1e8;
                for (int k = i; k < j; k++) {//k最多到j-1,
                    f[i][j] = Math.min(f[i][j],f[i][k] + f[k+1][j] + a[j] - a[i-1]);
                }
            }
        }
        System.out.println(f[1][n]);
    }
}




题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static String[] p = new String[N];//n个字符串
    static String q[] = new String[N];//m个字符串
    static int[][] f = new int[N+10][N+10];////所有将a[1-i]变成b[1-j]的操作方式
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            p[i] = br.readLine();
        }

        for (int i = 1; i <= m; i++) {
            int res = 0;
            q[i] = br.readLine();
            char[] a = q[i].split(" ")[0].toCharArray();
            int limit = Integer.parseInt(q[i].split(" ")[1]);
            for (int j = 1; j <= n; j++) {//判断有多少个字符串和当前的字符串能够在限制的次数下匹配
                char[] b = p[j].toCharArray();
                if(limit_distance(a,b) <= limit){
                    res++;
                }
            }
            System.out.println(res);
        }

    }
    static int limit_distance(char[] a,char[] b){//a是询问的字符串,b是给定的字符串
        for (int i = 0; i <= b.length; i++) f[0][i] = i;
        for (int i = 0; i <= a.length; i++) f[i][0] = i;

        for (int i = 1; i <= a.length; i++) {
            for (int j = 1; j <= b.length; j++) {
                f[i][j] = Math.min(f[i-1][j]+1,f[i][j-1]+1);
                if(a[i-1]==b[j-1]) f[i][j] = Math.min(f[i][j],f[i-1][j-1]);
                else f[i][j] = Math.min(f[i][j],f[i-1][j-1]+1);
            }
        }
        return f[a.length][b.length];
    }
}




题目描述

blablabla

JAVA代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    /**
     * 状态计算分为三种情况
     * 删除:在删掉i之前a[i-1]和b[j]是相同的,用f[i-1][j]表示a[i-1]变成b[j]的操作方式的最小值,f[i-1][j]+1表示加一步删除的操作
     * 增加:在添加j之前a[i]和b[j-1]是相同的,用f[i][j-1]表示a[i]变成b[j-1]的操作方式的最小值,f[i][j-1]+1表示加一步添加的操作
     * 改:在添加i之前a[i-1]和b[j-1]是相同的,用f[i-1][j-1]表示a[i-1]变成b[j-1]的操作方式的最小值,如果相同a[i]和b[j]相同,f[i][j]不用,如果不同,f[i][j]=f[i-1][j-1]+1;
     * */
    static int N = 1010;
    static char[] a = new char[N];
    static char[] b = new char[N];
    static int [][] f = new int[N][N];//所有将a[1-i]变成b[1-j]的操作方式的最小值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().split(" ")[0]);
        String A = br.readLine();
        for (int i = 1; i <= n; i++) {
            a[i] = A.toCharArray()[i-1];
        }
        int m = Integer.parseInt(br.readLine().split(" ")[0]);
        String B = br.readLine();
        for (int i = 1; i <= m; i++) {
            b[i] = B.toCharArray()[i-1];
        }
        //        System.out.println(n+"   "+m);
        //初始化
        for (int i = 1; i <= m; i++) f[0][i] = i; //把a的前0个字母变成b的前i个字母,添加i次
        for (int i = 1; i <= n; i++) f[i][0] = i; //把a的前i个字母变成b的前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]);
                else f[i][j] = Math.min(f[i-1][j-1]+1,f[i][j]);
            }
        }
        System.out.println(f[n][m]);
    }
}



新鲜事 原文



新鲜事 原文

不得不说,JAVA在数据多的时候使用BufferedReader读取比Scanner读取快太多了,同一个程序使用两个读取方法速度能差4倍多



题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static char[] a = new char[N];
    static char[] b = new char[N];
    static int[][] f = new int[N][N];//所有a[1-i]和b[1-j]的公共子序列的集合的最大值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        String A = br.readLine();
        String B = br.readLine();
        for (int i = 1; i <= A.length(); i++) {
            a[i] = A.toCharArray()[i-1];
        }
        for (int i = 1; i <=B.length() ; i++) {
            b[i] = B.toCharArray()[i-1];
        }
        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]);//不相等的时候,两个字符一定有一个可以抛弃,可以对f[i-1][j],f[i][j-1]两种状态取max。
                if(a[i] == b[j]) f[i][j] = Math.max( f[i][j] , f[i-1][j-1]+1);//如果相同 f[i][j] = f[i - 1][j - 1] + 1
            }
        }
        System.out.println(f[n][m]);
    }
}




题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    //进来一个数q[i]时,通过二分在f[]中找到最大的小于q[i]的数,就能够将qi接到该数的后面,即更新f[r + 1] = q[i]
    static int N = 100010;
    static int q[] = new int[N];
    static int f[] = new int[N];//所有不同长度上升子序列的结尾的最小值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            q[i] = Integer.parseInt(s[i-1]);
        }
        int len = 0;//当前的最大长度,也就是f[]里面的最大个数,初始是0
        f[1] = (int) -2e9;//

        for (int i = 1; i <= n; i++) {
            int l =0;int r = len;
            while (l < r){ //二分 找小于某个数的最大的数
                int mid = l+r+1 >> 1;
                if(f[mid] < q[i]) l = mid;//f[] 是找找小于q[i]的最大的数,如果f[mid] < q[i],说明还没找到距离q[i]的最近的最大的数,继续向右找
                else r = mid-1;
            }
            len = Math.max(len , r+1); // r找的是可以接在哪个数的后面,也就是目前哪个数的比它小的数里面的最大值,找到以后加1
            f[r + 1] = q[i];//r+1长度的上升子序列 的 结尾的最小值 是 q[i]
        }
        System.out.println(len);
    }
}




题目描述

blablabla

JAVA 代码



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    static int INF = 0x3f3f3f3f;
    static int N = 510;
    static int p[][] = new int[N][N];
    static int f[][] = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                f[i][j] = -INF;
            }
        }
        f[1][1] = p[1][1] = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            String s[] = br.readLine().split(" ");
            for (int j = 1; j <= i; j++) {
                p[i][j] = Integer.parseInt(s[j-1]);
                f[i][j] = Math.max(f[i-1][j-1],f[i-1][j])+p[i][j];
            }
        }
        int res = -INF;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res,f[n][i]);
        }
        System.out.println(res);

    }
}




题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 110;
    static int[][] v = new int[N][N];
    static int[][] w = new int[N][N];
    static int[] s = new int[N];
    static int[][] f = new int[N][N];//只从前i组选,且总体积不大于j的所有选法
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int V = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(br.readLine());
            for (int j = 1; j <= s[i]; j++) {
                String s2[] = br.readLine().split(" ");
                v[i][j] = Integer.parseInt(s2[0]);
                w[i][j] = Integer.parseInt(s2[1]);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                //不选第i组物品
                f[i][j] = f[i-1][j];
                for (int k = 1; k <= s[i]; k++) {//第i组物品有几个物品
                    //选第i组物品,选哪个
                    if(j >= v[i][k]) f[i][j] = Math.max(f[i][j],f[i-1][j-v[i][k]] + w[i][k]);
                }
            }
        }
        System.out.println(f[n][V]);
    }
}




题目描述

blablabla

JAVA代码



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    /**
     * 1.为什么不能用完全背包问题的思路去解决
     * 因为完全背包没有物品个数限制,所以只要体积够用就可以一直选,没有最后一项。
     * 完全背包最后那一项体积是刚好用完了的,而多重背包最后那一项之后还有体积没用完,所以多重背包的式子后面还可以多减一项,而完全背包就不行了。
     * 2.优化方法及代码
     *
     *
     * 3.01背包问题的优化写法
     * https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84-%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84
     * @param args
     */
    static int N = 12010;
    static int M = 2010;
    static int v[] = new int[N];
    static int w[] = new int[N];//
    static int f[] = new int[M];//体积小于M
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);//物品种数
        int m = Integer.parseInt(s1[1]);//背包容积。
        int cnt = 0;//分组的组别
        for (int i = 1; i <= n; i++) {
            String ss[] = br.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            int s = Integer.parseInt(ss[2]);
            int k = 1;//组别里面的个数
            /**
             * 第一个组1
             * 第二个组2
             * 第三个组4
             * 第四个组8
             * ...
             */
            while (k <= s){
                cnt++;//组别数先增加
                v[cnt] = a*k;//这个组的整体体积
                w[cnt] = b*k;//这个组的整体价值
                s -= k;//s减小
                k *= 2;//组别数成倍增加
            }
            //剩余的最后一组
            if(s>0){
                cnt++;
                v[cnt] = a*s;
                w[cnt] = b*s;
            }
        }

        n = cnt;//我们每次要枚举的是组数
        //优化后的01背包
        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.println(f[m]);
    }
}