首页 > 试题广场 >

消消乐

[编程题]消消乐
  • 热度指数:1645 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小v在vivo手机的应用商店中下载了一款名为“一维消消乐”的游戏,介绍如下:
1、给出一些不同颜色的豆子,豆子的颜色用数字(0-9)表示,即不同的数字表示不同的颜色;
2、通过不断地按行消除相同颜色且连续的豆子来积分,直到所有的豆子都消掉为止;
3、假如每一轮可以消除相同颜色的连续 k 个豆子(k >= 1),这样一轮之后小v将得到 k*k 个积分;
4、由于仅可按行消除,不可跨行或按列消除,因此谓之“一维消消乐”。
请你帮助小v计算出最终能获得的最大积分。


输入描述:
输入一行n个正整数,代表这一行中豆子的颜色及排列。

示例:

输入:1 4 2 2 3 3 2 4 1
输出:21

示例说明:
第一轮消除3,获得4分,序列变成1 4 2 2 2 4 1
第二轮消除2,获得9分,序列变成1 4 4 1
第三轮消除4,获得4分,序列变成1 1
第四轮消除1,获得4分,序列为空
总共得分21分


输出描述:
小V最终能拿到的最大积分。
示例1

输入

1 4 2 2 3 3 2 4 1

输出

21
使用动态规划求解
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];
    }
}


发表于 2021-02-09 17:22:09 回复(0)
人在vivo,刚刷完自己公司的题目。

高效的解法应当是动态规划,但是没那么多时间想,这里使用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)
            );
        }
    }


编辑于 2020-03-01 13:00:56 回复(6)
// 参照中大老哥思路做的
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;
    }
 
    private static int solution(int[] input) {
        // TODO Write your code here
        if(input == null || input.length == 0){
                   return 0;
        }
        int len = input.length;
        return DFS(input, len);
    }
     
    public static int DFS(int[] arr, int len){
             if(len == 1){
                 return 1;
             }
             if(len == 2){
                 if(arr[0] == arr[1]){
                     return 4;
                 }else{
                     return 2;
                 }
             }
             int max = 0;
             int L = 0;
             for(int i = 1; i < len; i++){
                   if(arr[i] != arr[L]){
                        int[] copy = new int[len - (i - L)];
                        int j = 0;
                        for(; j < L; j++){
                            copy[j] = arr[j];
                        }
                        for(int r = i; r < len; r++){
                            copy[j++] = arr[r];
                        }
                        max = Math.max(max, DFS(copy, copy.length) + (i - L)*(i - L));
                        L = i;
                   }
             }
             if(L == 0){
                 return len * len;
             }
             int[] copy = new int[L];
             for(int j = 0; j < L; j++){
                   copy[j] = arr[j];
             }
             max = Math.max(max, DFS(copy, copy.length) + (len - L) * (len - L));
             return max;
    }
}
发表于 2019-12-31 20:57:21 回复(0)
/*
遍历递归
*/
#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

/**
 * Welcome to vivo !
 */

#define MAX_NUM 100

int solution(int boxs[], int N)
{
//	cout << "N = " << N << endl;
	if(N <= 0)	return 0;
//	if(N == 1){
//		return 1;
//	}
//	if(N == 2){
//		if(boxs[0] == boxs[1])	return 4;
//		else return 2;
//	}
	int S=0,E=0;
	int max =1,temp;
    for(int i = 1;i<N;i++){
//    	cout << "!" << endl;
    	if(boxs[i] == boxs[S]){
    		E++;	
//    		cout << "S";
		}
		if(boxs[i] != boxs[S]){
//			cout << "D";
			int copy[N];
			int j = 0;
		    for(int p = 0;p<S;p++,j++){
				copy[j] = boxs[p];
//				cout << copy[j] << " ";
			}
			for(int p = E+1;p<N;p++,j++){
				copy[j] = boxs[p];
//				cout << copy[j] << " ";
			}
//			cout << endl;
			int Z = solution(copy,N-(E-S+1));
    		temp = (E-S+1)*(E-S+1) + Z;
//    		cout << "temp = " << (E-S+1)*(E-S+1) << "+" << Z << endl;
    		max = temp>max?temp:max;
//    		cout << "max = " << max << endl;
    		S = E+1;
    		E = E+1;
		}
	}
	if(S == 0 && E == (N-1)){
		return (E-S+1)*(E-S+1);
	}
	//1 2 2 1
	return max;
}

int main()
{
	string str("");
	getline(cin, str);
	int boxs[MAX_NUM];
	int i = 0;
	char *p;
	int count = 0;
	
	const char* strs = str.c_str();
	p = strtok((char *)strs, " ");
	while(p)
	{
		boxs[i] = atoi(p);
		count++;
		p = strtok(NULL, " ");
		i++;
		if(i >= MAX_NUM)
			break;
	}

	int num = solution(boxs, count);
	cout << num << endl;
	return 0;
}

发表于 2019-12-28 13:37:02 回复(7)
暴力:
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]);
        }
    }

}

编辑于 2024-01-24 09:36:55 回复(0)
#!/usr/bin/python
# -*- coding: utf-8 -*-

'''
Welcome to vivo !
'''

def solution(boxes):
    max_rst = 0
    memo = {}
    
    def dfs(state):
        nonlocal max_rst, memo
        #print(state)
        if not state: # 已经全取出来了,返回0
            return 0
        i = 0
        rst = 0 # 保存在当前状态下的最高分数
        while 1:
            if i == len(state):
                break
            c = state[i]
            j = i+1
            while(j < len(state) and state[j]==c): # 找连续相同子串
                j+=1
            next_state = state[:i]+state[j:] # 下一个状态
            now_score = (j-i)**2 # 当前步骤的得分

            t_state = tuple(next_state) # list 转 tuple,才能hash
            if t_state not in memo.keys(): # 记忆化
                memo[t_state] = dfs(next_state)
            rst = max(rst, now_score + memo[t_state]) #当前操作得分+剩余状态的得分 找最大值

            i = j
        return rst
    
    return dfs(boxes)


if __name__ == '__main__':
    x = input()
    boxes = list(map(int,x.split()))
    print(solution(boxes))
dfs + 对重复状态的记忆, 应该非常直观粗暴了
编辑于 2020-06-06 01:24:21 回复(0)