第8章 枚举算法

1、四平方和

算法分析

暴力做法，枚举a，b，c，算出d，判断d是不是某个数的平方

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        //预处理
        for(int a = 0;a * a<= n;a ++)
            for(int b = a;a * a + b * b <= n;b ++)
                for(int c = b;a * a + b * b + c * c <= n;c ++)
                {
                    //巧妙方法，判定某个数是否能用其他数的平方表示出来
                    int t = n - a * a - b * b - c * c;
                    int d = (int)Math.sqrt(t);
                    if(d * d == t)
                    {
                        System.out.println(a + " " + b + " " + c + " " + d);
                        return;
                    }
                }
    }
}

2、装饰效果

算法分析

求最大区间和问题，dp

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    static int N = 1010;
    static int[] f = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 1;i <= n;i ++)
            f[i] = scan.nextInt();
        
        int ans = 0;
        //求最大区间和
        for(int i = 1;i <= n;i ++)
        {
            f[i] = Math.max(f[i - 1] + f[i], f[i]);
            ans = Math.max(f[i], ans);
        }
        System.out.println(ans);
    }
}

3、奖劵数目

算法分析

感觉可以用数位dp，到时候试下
枚举 [n,m] 范围内的所有整数，对每个整数 x，取出它的每一位，判断是否有 4。如果每位都不存在 4，答案就加一。

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    static int N = 1010;
    static int[] f = new int[N];
    static boolean check(int x)
    {
        while(x > 0)
        {
            if(x % 10 == 4) return false;
            x /= 10;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int res = 0;
        for(int i = n;i <= m;i ++)
        {
            if(check(i)) res ++;
        }
        System.out.println(res);
    }
}

4、双节棍

算法分析

选长度相差最短的两个棍子，排序，求差分，求出相邻两个数的差值的最下值

时间复杂度

Java 代码

import java.util.Arrays;
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 scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
        Arrays.sort(a,1,n + 1);
        int res = 10000;
        for(int i = 2;i <= n;i ++) 
        {
            f[i] = a[i] - a[i - 1];
            res = Math.min(res, f[i]);
        }
        System.out.println(res);
        
    }
}

5、北极圈远征

算法分析

52 * (7x + 21k) = n，x从100枚举到1，k算一下上界是400，从1枚举到400

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int x = 100;x >= 1;x --)
        {
            for(int k = 1;k <= 400;k ++)
            {
                if(52 * (7 * x + 21 * k) == n) 
                {
                    System.out.println(x);
                    System.out.println(k);
                    return;
                }
            }
        }
    }
}

6、最大子阵和

算法分析

求最大子阵和问题，前缀和

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    static int N = 55;
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
            {
                f[i][j] = scan.nextInt();
                f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] ;
            }
        int res = -1000;
        for(int x1 = 1; x1 <= n;x1 ++)
            for(int y1 = 1;y1 <= m;y1 ++)
                for(int x2 = 1;x2 <= x1;x2 ++)
                    for(int y2 = 1;y2 <= y1;y2 ++)
                    {
                        int v = f[x1][y1] - f[x2 - 1][y1] - f[x1][y2 - 1] + f[x2 - 1][y2 - 1];
                        res = Math.max(res,v);
                    }
        System.out.println(res);
        
    }
}