消消乐

人在vivo，刚刷完自己公司的题目。

这题是Leetcode原题：https://leetcode.com/problems/remove-boxes/

高效的解法应当是动态规划，但是没那么多时间想，这里使用dancing links的思想，使用一个链表记录数组，然后回溯即可

import java.io.*;
 
/**
 * Welcome to vivo !
 */
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int input[] = parseInts(inputStr.split(" "));
        int output = solution(input);
        System.out.println(output);
    }
 
    private static int[] parseInts(String[] strArr) {
        if (strArr == null || strArr.length == 0) {
            return new int[0];
        }
        int[] intArr = new int[strArr.length];
        for (int i = 0; i < intArr.length; i++) {
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        return intArr;
    }
     
    static class Node {
        Node prev;
        Node next;
        int val;
        Node(int val){
            this.val = val;
        }
    }
 
    private static int solution(int[] input) {
        // TODO Write your code here
        Node head = new Node(0);
        Node node = head;
        for(int i=0;i<input.length;++i){
            Node  p = new  Node(input[i]);
            p.prev = node;
            node.next = p;
            node = p;
        }
        return search(head);
    }
    static int search(Node head){
        if(head.next == null)return 0;
         
        int max = 0;
        Node p=head.next;
        while(p!=null){
            Node r=p;
            int c=1;
            while(r.next!=null && r.next.val==r.val){ r=r.next; ++c;} 
            // remove
            p.prev.next = r.next;
            if(r.next!=null)r.next.prev=p.prev;
            int val = c*c + search(head);
            // restore
            p.prev.next = p;
            if(r.next!=null)r.next.prev=r;
            max = Math.max(max,val);
             
            p = r.next;
        }
         
        return max;
    }
}

Leetcode原题的dp解法：

class Solution {
        int n;
        int[][] F;
        int[] prev;

        public int removeBoxes(int[] boxes) {
            n = boxes.length;
            prev = new int[n];
            F = new int[n][n];
            for (int i = 0; i < n; i++) {
                prev[i] = -1;
                for (int j = 0; j < n; j++) {
                    F[i][j] = -1;
                }
                for (int j = i - 1; j >= 0; --j) {
                    if (boxes[i] == boxes[j]) {
                        prev[i] = j;
                        break;
                    }
                }
            }
            return f(0, n - 1);
        }

        public int f(int i, int j) {
            if (i > j) {
                return 0;
            }
            if (F[i][j] != -1) {
                return F[i][j];
            }
            if (i == j) {
                return F[i][j] = 1;
            }
            return F[i][j] = g(i, j, prev[j], 1);
        }


        public int g(int i, int j, int r, int m) {
            if (i > j) {
                return 0;
            }
            if (r < i) {
                return f(i, j - 1) + m * m;
            }
            // 如果相邻，可以消除许多中间状态
            if (r + 1 == j) {
                return g(i, r, prev[r], m + 1);
            }
            int rv = prev[r];
            return Math.max(
                    g(i, r, rv, m + 1) + f(r + 1, j - 1),
                    g(i, j, rv, m)
            );
        }
    }

leetcode第546题“移除盒子”原题：https://leetcode-cn.com/problems/remove-boxes/solution/yi-chu-he-zi-by-leetcode-solution/

使用动态规划求解

import java.io.*;

/**
 * Welcome to vivo !
 */

public class Main {
    private static int[][][] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int input[] = parseInts(inputStr.split(" "));
        int output = solution(input);
        System.out.println(output);
    }

    private static int[] parseInts(String[] strArr) {
        if (strArr == null || strArr.length == 0) {
            return new int[0];
        }
        int[] intArr = new int[strArr.length];
        for (int i = 0; i < intArr.length; i++) {
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        return intArr;
    }

    private static int solution(int[] input) {
        // TODO Write your code here
        int length = input.length;
        dp = new int[length][length][length];
        return calculatePoints(input, 0, length - 1, 0);
    }
    
    public static int calculatePoints(int[] boxes, int l, int r, int k) {
        if (l > r) return 0;
        if (dp[l][r][k] == 0) {
            dp[l][r][k] = calculatePoints(boxes, l, r - 1, 0) + (k + 1) * (k + 1);
            for (int i = l; i < r; i++) {
                if (boxes[i] == boxes[r])
                    dp[l][r][k] = Math.max(dp[l][r][k], calculatePoints(boxes, l, i, k + 1) + calculatePoints(boxes, i + 1, r - 1, 0));
            }
        }
        return dp[l][r][k];
    }
}

暴力：

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * Welcome to vivo !
 */

public class Main {
    public static int mNums = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int input[] = parseInts(inputStr.split(" "));
        int output = solution(input);
        System.out.println(output);
    }

    private static int[] parseInts(String[] strArr) {
        if (strArr == null || strArr.length == 0) {
            return new int[0];
        }
        int[] intArr = new int[strArr.length];
        for (int i = 0; i < intArr.length; i++) {
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        return intArr;
    }

    private static int solution(int[] input) {

        // TODO Write your code here
        List<Integer> src = new ArrayList<>();
        listAddInteger(src, input);
        a120(src, 0);
        return mNums;
    }

    public static void a120(List<Integer> src, int result) {
        if (src.isEmpty()) {
            return;
        }
        int k = 0;
        int curVal = 0;
        for (int i = 0; i < src.size(); i++) {
            int tmp = src.get(i);
            if (i == src.size() - 1) {
                if (tmp == curVal) {
                    mNums = Math.max(mNums, result + (k + 1) * (k + 1));
                } else {
                    mNums = Math.max(mNums, result + k * k + 1);
                }
            }
            if (tmp != curVal) {
                if (k == 0) {
                    k++;
                    curVal = tmp;
                } else {
                    List<Integer> tmpArrays = new ArrayList<>();
                    tmpArrays.addAll(src);
                    for (int j = 0; j < k; j++) {
                        tmpArrays.remove(i - k);
                    }
                    a120(tmpArrays, result + k * k);
                    k = 1;
                    curVal = tmp;
                }
            } else {
                k++;
            }
        }
    }

    public static void listAddInteger(List<Integer> list, int[] arrays) {
        for (int i = 0; i < arrays.length; i++) {
            list.add(arrays[i]);
        }
    }

}