头像

j简单




离线:8小时前


活动打卡代码 AcWing 1212. 地宫取宝

j简单
17小时前

【题目描述】

AcWing 1212. 地宫取宝

暴力DFS

时间复杂度 O(2 ^(m*n))
只能通过 30%的数据


import java.util.Scanner;
public class Main{
    static int N = 55;
    static int n, m, k;
    static int [][]g = new int[N][N];
    static long ans = 0;
    static int p = 1000000007;
    static int dx[] = {1, 0};
    static int dy[] = {0, 1};

    public static void dfs(int x, int y, int curMax, int cnt){
        //System.out.println(x + " "+ y + " "+ min + " "+ cnt);
        //已经走到右下角
        if( x == n - 1 && y == m - 1 )
        {
            //如果宝贝个数等于k 
            if( cnt == k)  ans = (ans + 1) % p;
            return;
        }

        for(int i = 0; i < 2; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if( a >= 0 && a < n && b >= 0 && b < m)//合法位置
            {   

                //(a,b)位置的宝贝比已有的都大 可以考虑是否拿起
                if( g[a][b] > curMax && cnt < k )
                {  
                    dfs(a, b, g[a][b], cnt + 1);//拿起

                }
                dfs(a, b, curMax, cnt);
            }
        }
    }
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        n = reader.nextInt();
        m = reader.nextInt();
        k = reader.nextInt();
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                g[i][j] = reader.nextInt();

        dfs(0, 0, - 1, 0);//(0,0)位置不宝物选

        dfs(0, 0, g[0][0], 1); // (0,0)位置宝物选

        System.out.println(ans);
    }
}

动态规划

【思路】
最长上升子序列 摘花生问题的综合
在这里插入图片描述

import java.util.Scanner;

public class Main  {
    static int n,m,k;
    static final int mod=1000000007;
    static int N = 55;
    static int w[][] =new int[N][N];
    static int f[][][][] = new int[N][N][13][14];//x 、 y 、k、 c


    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        n=reader.nextInt();
        m=reader.nextInt();
        k=reader.nextInt();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                w[i][j]=reader.nextInt() + 1; //将价值范围变为1~13
            }
        }
        f[1][1][1][w[1][1]] = 1;  //(1,1)位置取宝贝
        f[1][1][0][0] = 1;      //(1,1)位置不取宝贝  c为0
        long res = 0;

        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                if( i == 1 && j == 1) continue;
                for(int u = 0; u <= k; u ++)//
                {
                    for(int v = 0; v <= 13; v ++)
                    {
                        f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u][v]) % mod;
                        f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u][v]) % mod;
                        if( u > 0 && w[i][j] == v)
                        {
                            for(int c = 0; c < v; c ++)
                            {
                                f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u - 1][c]) % mod;
                                f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u - 1][c]) % mod;
                            }
                        }
                    }
                }
            }
        for(int i = 0; i <= 13; i ++)
            res = (res + f[n][m][k][i])%mod;

        System.out.println(res);

    }

}



j简单
21小时前

【题目描述】

在这里插入图片描述

AcWing 895. 最长上升子序列

【思路】

动态规划
在这里插入图片描述
7
3 1 2 1 8 5 6

原序列为 a,状态数组为f。
状态表示:
f[i]表示一个状态集合,该集合为所有以第i个元素结尾的上升子序列。例如f[4],其上升子序列集合为{ {3,8},{1,8}, {2,8},{1,2,8} }。f[i]的属性值为集合元素的最大长度,表示以第i个元素结尾的最长上升子序列长度。

状态转移:
以第i - 1个数 是原序列的哪个数来划分f[i]状态表示的集合,第i - 1个数可以是原序列的第 0 、 1 …… i - 1。那么求出每一个元素,取长度的max。
f[i] = max(f[j]) , j = 0, 1……i - 1且a[i] > a[j]

/*
  3 1 2 1 8 5 6
0 1 1 2 2 3 3 4
1 2 5 6 
*/
import java.util.Scanner;
public class Main{
    static int N = 1010;
    static int a[] = new int[N]; //原序列
    static int f[] = new int[N]; //状态数组
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        for(int i = 0; i < n; i ++) a[i] = reader.nextInt();

        //以第0个元素结尾的最长上升子序列长度为1
        f[0] = 1;
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < i; j ++)
            {
                if(a[i] > a[j]) f[i] = Math.max(f[i], f[j] + 1);
                else f[i] = Math.max(f[i], 1);

            }
        }
        int ans = f[0];
        for(int i = 1; i < n; i ++)
            if(f[i] > ans)
                ans = f[i];
        System.out.println(ans);
    }
}

DFS

TLE 只过了两个数据

import java.util.Scanner;
public class Main{
    static int N = 1010;
    static int f[] = new int[N];
    static int n, ans = Integer.MIN_VALUE;
    public static boolean check(int bestf[], int len){
        for(int i = 2; i <= len; i ++)//非严格递增序列
            if(bestf[i] <= bestf[i - 1]) return false;
        return true;
    }
    public static void dfs(int m, int len, int[]bestf){
        if( m == n){
            //递增序列 且长度大于ans则更新
            if(len > ans && check(bestf,len)) ans = len;
            return;
        }
        //第m个元素选
        bestf[len + 1] = f[m];
        dfs(m + 1, len + 1, bestf);

        //第m个元素不选
        dfs(m + 1, len, bestf);
    }
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        n = reader.nextInt();
        for(int i = 0; i < n; i ++) f[i] = reader.nextInt();
        int [] bestf = new int[n + 1];
        dfs(0, 0, bestf);
        System.out.println(ans);
    }
}



j简单
21小时前

【题目描述】

在这里插入图片描述

AcWing 895. 最长上升子序列

【思路】

动态规划
在这里插入图片描述
7
3 1 2 1 8 5 6

原序列为 a,状态数组为f。
状态表示:
f[i]表示一个状态集合,该集合为所有以第i个元素结尾的上升子序列。例如f[4],其上升子序列集合为{ {3,8},{1,8}, {2,8},{1,2,8} }。f[i]的属性值为集合元素的最大长度,表示以第i个元素结尾的最长上升子序列长度。

状态转移:
以第i - 1个数 是原序列的哪个数来划分f[i]状态表示的集合,第i - 1个数可以是原序列的第 0 、 1 …… i - 1。那么求出每一个元素,取长度的max。
f[i] = max(f[j]) , j = 0, 1……i - 1且a[i] > a[j]

/*
  3 1 2 1 8 5 6
0 1 1 2 2 3 3 4
1 2 5 6 
*/
import java.util.Scanner;
public class Main{
    static int N = 1010;
    static int a[] = new int[N]; //原序列
    static int f[] = new int[N]; //状态数组
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        for(int i = 0; i < n; i ++) a[i] = reader.nextInt();

        //以第0个元素结尾的最长上升子序列长度为1
        f[0] = 1;
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < i; j ++)
            {
                if(a[i] > a[j]) f[i] = Math.max(f[i], f[j] + 1);
                else f[i] = Math.max(f[i], 1);

            }
        }
        int ans = f[0];
        for(int i = 1; i < n; i ++)
            if(f[i] > ans)
                ans = f[i];
        System.out.println(ans);
    }
}

DFS

TLE 只过了两个数据

import java.util.Scanner;
public class Main{
    static int N = 1010;
    static int f[] = new int[N];
    static int n, ans = Integer.MIN_VALUE;
    public static boolean check(int bestf[], int len){
        for(int i = 2; i <= len; i ++)//非严格递增序列
            if(bestf[i] <= bestf[i - 1]) return false;
        return true;
    }
    public static void dfs(int m, int len, int[]bestf){
        if( m == n){
            //递增序列 且长度大于ans则更新
            if(len > ans && check(bestf,len)) ans = len;
            return;
        }
        //第m个元素选
        bestf[len + 1] = f[m];
        dfs(m + 1, len + 1, bestf);

        //第m个元素不选
        dfs(m + 1, len, bestf);
    }
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        n = reader.nextInt();
        for(int i = 0; i < n; i ++) f[i] = reader.nextInt();
        int [] bestf = new int[n + 1];
        dfs(0, 0, bestf);
        System.out.println(ans);
    }
}


活动打卡代码 AcWing 1015. 摘花生

j简单
1天前

【题目描述】
AcWing 1015. 摘花生

【思路】
DFS
TLE 只通过了两个数据

import java.io.*;
class Main{
    static int N = 110;
    static int q[][] = new int[ N ][ N ];
    static int R, C;
    static int dir[][]  = { {0, 1}, {1, 0}};
    static boolean st[][] = new boolean[N][N];
    static int ans = Integer.MIN_VALUE;
    public static void dfs(int x, int y, int res ){

        if( x == R && y == C ){
            if( res > ans) ans = res;
            return;
        }        
        for(int i = 0; i < 2; i ++)
        {
            int a = x + dir[i][0], b = y + dir[i][1];
            if( a >=1 && a <= R && b >= 1 && b <= C)
            {
                st[a][b] = true;
                dfs(a, b, res + q[a][b]);
                st[a][b] = false;
            }
        }
    }
    public static void main(String args[]) throws Exception{
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(bf.readLine());
        while(T-- > 0){
            String str[] = bf.readLine().split(" ");
            R = Integer.parseInt(str[0]);
            C = Integer.parseInt(str[1]);

            for(int i = 1; i <= R; i++){
                String s[] = bf.readLine().split(" ");
                for(int j = 1; j <= C; j++) q[i][j] = Integer.parseInt(s[ j -1 ]);
            }
            ans = 0;
            st[1][1] = true;
            dfs(1, 1, q[1][1]);
            System.out.println(ans);
            }
        bf.close();
    }
}

【思路】
动态规划
当前格子是从左边来的也可能是上边来的,不论是哪种决策。要想从西北角开始,都选择上一步决策所带来的的较大花生数者。

import java.io.*;
class Main{
    static int M = 110, N = 110;

    public static void main(String args[]) throws Exception{
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(bf.readLine());
        while(T-- > 0){
            String str[] = bf.readLine().split(" ");
            int R = Integer.parseInt(str[0]), C = Integer.parseInt(str[1]);
            int q[][] = new int[ M ][ N ];
            for(int i = 1; i <= R; i++){
                String s[] = bf.readLine().split(" ");
                for(int j = 1; j <= C; j++) q[i][j] = Integer.parseInt(s[ j -1 ]);
            }
            int f[][] = new int[ M ][ N];
            for(int i = 1; i <= R; i++)
                for(int j = 1; j <= C; j++)
                    f[i][j] =  Math.max(f[i - 1][j], f[i][j - 1]) + q[i][j];
            log.write(f[R][C]+"");
            log.write("\n");
        }
        log.flush();
        log.close();
        bf.close();
    }
}

[HTML_REMOVED]
如果是从后向前状态转移方程式:for(int i = r; i >= 1; i–) for(int j = c; j >= 1; j–) f[i][j] = max(f[i+1][j], f[i][j+1])+a[i][j];,即从下往上,从右往左更新,输出f[1][1]
而不是:for(int i = r; i >= 1; i–) for(int j = c; j >= 1; j–) f[i][j] = max(f[i-1][j], f[i][j-1])+q[i][j];
[HTML_REMOVED]




j简单
1天前

【题目描述】
AcWing 1015. 摘花生

【思路】
DFS
TLE 只通过了两个数据

import java.io.*;
class Main{
    static int N = 110;
    static int q[][] = new int[ N ][ N ];
    static int R, C;
    static int dir[][]  = { {0, 1}, {1, 0}};
    static boolean st[][] = new boolean[N][N];
    static int ans = Integer.MIN_VALUE;
    public static void dfs(int x, int y, int res ){

        if( x == R && y == C ){
            if( res > ans) ans = res;
            return;
        }        
        for(int i = 0; i < 2; i ++)
        {
            int a = x + dir[i][0], b = y + dir[i][1];
            if( a >=1 && a <= R && b >= 1 && b <= C)
            {
                st[a][b] = true;
                dfs(a, b, res + q[a][b]);
                st[a][b] = false;
            }
        }
    }
    public static void main(String args[]) throws Exception{
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(bf.readLine());
        while(T-- > 0){
            String str[] = bf.readLine().split(" ");
            R = Integer.parseInt(str[0]);
            C = Integer.parseInt(str[1]);

            for(int i = 1; i <= R; i++){
                String s[] = bf.readLine().split(" ");
                for(int j = 1; j <= C; j++) q[i][j] = Integer.parseInt(s[ j -1 ]);
            }
            ans = 0;
            st[1][1] = true;
            dfs(1, 1, q[1][1]);
            System.out.println(ans);
            }
        bf.close();
    }
}

【思路】
动态规划
当前格子是从左边来的也可能是上边来的,不论是哪种决策。要想从西北角开始,都选择上一步决策所带来的的较大花生数者。

import java.io.*;
class Main{
    static int M = 110, N = 110;

    public static void main(String args[]) throws Exception{
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(bf.readLine());
        while(T-- > 0){
            String str[] = bf.readLine().split(" ");
            int R = Integer.parseInt(str[0]), C = Integer.parseInt(str[1]);
            int q[][] = new int[ M ][ N ];
            for(int i = 1; i <= R; i++){
                String s[] = bf.readLine().split(" ");
                for(int j = 1; j <= C; j++) q[i][j] = Integer.parseInt(s[ j -1 ]);
            }
            int f[][] = new int[ M ][ N];
            for(int i = 1; i <= R; i++)
                for(int j = 1; j <= C; j++)
                    f[i][j] =  Math.max(f[i - 1][j], f[i][j - 1]) + q[i][j];
            log.write(f[R][C]+"");
            log.write("\n");
        }
        log.flush();
        log.close();
        bf.close();
    }
}

[HTML_REMOVED]
如果是从后向前状态转移方程式:for(int i = r; i >= 1; i–) for(int j = c; j >= 1; j–) f[i][j] = max(f[i+1][j], f[i][j+1])+a[i][j];,即从下往上,从右往左更新,输出f[1][1]
而不是:for(int i = r; i >= 1; i–) for(int j = c; j >= 1; j–) f[i][j] = max(f[i-1][j], f[i][j-1])+q[i][j];
[HTML_REMOVED]




j简单
1天前

【题目描述】
AcWing 2. 01背包问题

【思路】
经典01背包。
f[i][j]表示前i个物品 容量不超过j的最大价值
状态转移:注意是当前行是从上一行转移过来的
j < v[i] 时, f[i][j] = f[i - 1][j]
j >= v[i]时,f[i][j] = max(不选第i号物品,选第i号物品) = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])


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

        for(int i = 1; i <= N; i ++)//物品下标从1开始
            for(int j = 0; j <= V; j ++)
            {
                if(j < v[i]) f[i][j] = f[i - 1][j];
                //不选、选第i号物品
                else    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            }

        System.out.println(f[N][V]);
    }
}


活动打卡代码 AcWing 2. 01背包问题

j简单
1天前

【题目描述】
AcWing 2. 01背包问题

【思路】
经典01背包。
f[i][j]表示前i个物品 容量不超过j的最大价值
状态转移:注意是当前行是从上一行转移过来的
j < v[i] 时, f[i][j] = f[i - 1][j]
j >= v[i]时,f[i][j] = max(不选第i号物品,选第i号物品) = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])


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

        for(int i = 1; i <= N; i ++)//物品下标从1开始
            for(int j = 0; j <= V; j ++)
            {
                if(j < v[i]) f[i][j] = f[i - 1][j];
                //不选、选第i号物品
                else    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            }

        System.out.println(f[N][V]);
    }
}


活动打卡代码 AcWing 1216. 饮料换购

j简单
1天前

【题目描述】
在这里插入图片描述

AcWing 1216. 饮料换购

【思路】

手动模拟一遍

0瓶盖 100瓶
100瓶盖/3 = 33瓶 ……1瓶盖
34 瓶盖/3 = 11瓶 ……1瓶盖
11 + 1瓶盖/3 = 4瓶……0瓶盖
4瓶盖 / 3 = 1瓶 …… 1瓶盖
1 + 1 < 3 return 0
100 + 11 + 33 + 4 = 14

35
35瓶盖 / 3 = 11瓶 …… 2瓶盖
13瓶盖 / 3 = 4瓶 …… 1瓶盖
5瓶盖 / 3 = 1瓶 …… 2瓶盖
3瓶盖 / 3 = 1瓶 …… 0瓶盖


import java.util.Scanner;
class Main{
    /*
    m:下次瓶盖数 = 本次兑换瓶数 + 本次剩余瓶盖数
    n:当前可以兑换的瓶数
    */
    public static int ans = 0;
    public  static void dfs(int m, int n){
        ans += n;
        if( m  < 3) return;
        dfs(m / 3 + m % 3, m / 3);
    }
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        //下次瓶盖数数为n  本次瓶数为0
        dfs(n, 0);
        System.out.println(n + ans);

    }
}


活动打卡代码 AcWing 1211. 蚂蚁感冒

j简单
2天前

【题目描述】

AcWing 1211. 蚂蚁感冒

【思路】

在这里插入图片描述
在这里插入图片描述

import java.util.Scanner;
import java.lang.Math;
class Main{
    static int n;
    static int N = 55;
    static int f[] = new int[N];    //记录蚂蚁位置

    public static void main(String ags[]){
        Scanner reader = new Scanner(System.in);
        n = reader.nextInt();
        for(int i = 0; i < n; i++)
            f[i] = reader.nextInt();

        //相遇调头等价于 交换身份继续前进
        int left = 0, right = 0; //分别表示左边往右走的蚂蚁数量和右边往左走的蚂蚁数量
        for(int i = 1; i < n; i ++)
            if( Math.abs( f[i] ) > Math.abs( f[0] ) && f[i] < 0) right ++;
            else if( Math.abs( f[i] ) <Math.abs( f[0] ) && f[i] > 0 ) left ++;
        //第一只蚂蚁往左走且左边没有往左右走的蚂蚁  or 第一只蚂蚁往右走且右边没有往左走的蚂蚁
        if( (f[0] < 0 && left == 0 ) || (f[0] > 0 && right == 0))
            System.out.println( 1 );
        else
            System.out.println( left +right + 1 );

    }
}



j简单
2天前

【题目描述】

AcWing 1205. 买不到的数目

暴力枚举 迭代写法

【思路】
分别枚举m、n的个数
for(m个数)
for(n个数)
k = m * m个数 + n * n个数
O(N^2),只能枚举答案在1000以内的

import java.util.Scanner;
public class Main{
    static int N = 10010;
    static int []f = new int [N];
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt(), m = reader.nextInt();
        for(int i = 0; i < N / m + 1; i ++)//枚举m的个数
            for(int j = 0; j < N / n + 1; j++)//枚举n的个数
            {
                int k = m * i + n * j;
                if( k >= N ) continue;
                f[k] = 1;
            }
        for(int i = N - 1; i >= 0;i --)
            if(f[i] == 0){
                System.out.println(i);
                break;
            }
    }
}


暴力枚举——递归写法

过5/10数据

import java.util.Scanner;
public class Main{
    //判断x能否由m、n组成
    public  static boolean dfs(int x, int m, int n){

        if( x < 0) return false;

        //x == 0 说明x能由若干m、n组成
        if( x == 0 ) return true;

        if( x >= m && dfs(x - m, m, n)) return true;
        if( x >= n && dfs(x - n, m, n)) return true;

        return false;
    }
    public static void main(String args[]){

        Scanner reader = new Scanner(System.in);
        int m = reader.nextInt(), n = reader.nextInt();
        for(int i = 1000; i >= 1; i --)
        {
            if(!dfs(i, m, n)){
                System.out.println(i);
                break;
            }
        }

    }
}

错误写法:

对于有返回值的递归函数,要注意对中间结果的保存和处理,只是把它扔掉了

import java.util.Scanner;
public class Main{
    //判断x能否由m、n组成
    public  static boolean dfs(int x, int m, int n){

        if( x < 0) return false;

        //x == 0 说明x能由若干m、n组成
        if( x == 0 ) return true;

        if( x >= m ) return dfs(x - m, m, n);
        if( x >= n ) return dfs(x - n, m, n);

        return false;
    }
    public static void main(String args[]){

        Scanner reader = new Scanner(System.in);
        int m = reader.nextInt(), n = reader.nextInt();
        for(int i = 1000; i >= 1; i --)
        {
            if(!dfs(i, m, n)){
                System.out.println(i);
                break;
            }
        }

    }
}


AC代码

引理

给定a,b,如果d =gcd(a, b) >1,那么其凡不是d倍数的a,b都凑不出,因此其不存在最大的凑不出的数。

结论

若a、b均为正整数且gcd(a,b) = 1, 那么 ax + by ,x >= 0, y >= 0,最大不能表示的数为 a*b - a - b

import java.util.Scanner;
public class Main{

    public static void main(String args[]){

        Scanner reader = new Scanner(System.in);
        int a = reader.nextInt(), b = reader.nextInt();
        //公式: (a - 1) * (b - 1) - 1 =ab -a - b
        System.out.println(a * b - a - b);

    }
}