【蟻本】01ナップサック問題【Java】

【入力例】

4
2 1 3 2
3 2 4 2
5

【出力例】

7

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        for (int i=0; i<n; i++) {
            w[i] = sc.nextInt();
        }
        for (int i=0; i<n; i++) {
            v[i] = sc.nextInt();
        }
        int W = sc.nextInt();
        int[][] dp = new int[n+1][W+1];

        for (int i=n-1; i>=0; i--) {
            for (int j=0; j<=W; j++) {
                if (j<w[i]) {
                    dp[i][j] = dp[i+1][j];
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
                }
            }
        }
        System.out.println(dp[0][W]);
    }
}

【蟻本】Fance Repair【Java】

【入力例】

5
2 4 5 1 3

【出力例】

33

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List <Integer> L = new ArrayList<>();
        for (int i=0; i<N; i++) {
            L.add(sc.nextInt());
        }
        long ans = 0;
        int temp = 0;
        while (N > 1) {
            int mii1 = 0, mii2 = 1;
            if (L.get(mii1) > L.get(mii2)) {
                temp = mii1;
                mii1 = mii2;
                mii2 = temp;
            }

            for (int i= 2; i<N; i++) {
                if (L.get(i) < L.get(mii1)) {
                    mii2 = mii1;
                    mii1 = i;
                }
                else if (L.get(i) < L.get(mii2)) {
                    mii2 = i;
                }
            }

            int t = L.get(mii1) + L.get(mii2);
            ans += t;

            if (mii1 == N - 1) {
                temp = mii1;
                mii1 = mii2;
                mii2 = temp;
            }
            L.set(mii1, t);
            L.set(mii2, L.get(N-1));
            N--;
        }

        System.out.println(ans);
    }
}

【蟻本】Saruman's Army【Java】

【入力例】

6
10
1 7 15 20 30 50

【出力例】

3

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        int[] X = new int[N];
        for (int i=0; i<N; i++) {
            X[i] = sc.nextInt();
        }
        Arrays.sort(X);
        int i = 0, ans = 0;
        while (i < N) {
            int s = X[i++];
            while (i < N && X[i] <= s + R) i++;
            int p = X[i - 1];
            while (i < N && X[i] <= p + R) i++;

            ans++;
        }

        System.out.println(ans);
    }
}