构建最大的堆叠塔与集团和限制

Question

问题

问题是按照所有规则建造最高的圆柱塔。

将安排在table，数量N个柱面。
每个圆柱体只有一种颜色：红色、橙色、绿色或蓝色。
每个圆柱体的高度为 h，底面半径为 r。
要建塔，圆柱体要堆叠起来，顶部圆柱体的底部应该比顶部圆柱体的底部小它下面的圆柱体。除了第一个圆柱体，它可以有任何尺寸，因为它下面没有其他圆柱体。

对于圆柱体的颜色也有一些非常有趣的限制。它们在下面描述。

红色圆柱体不能放在橙色圆柱体上
橙色圆柱体不能放在蓝色圆柱体上
蓝色圆柱体不能放在绿色圆柱体上
绿色圆柱体不能放在红色圆柱体上

输入

The input contains several test cases. The first line of each test case contains an integer N (1 <= N <= 10^3), representing the number of cylinders arranged on the table, following N rows, each row having a height h (1 <= h <= 1000) of the cylinder in centimeters, the radius r (1 <= r <= 1000) of the cylinder base and a word p, representing the color of the cylinder. The word can be: RED, ORANGE, GREEN, or BLUE. The end of input is indicated as N = 0, which should not be processed.

输出

For each test case, your program should print a single line with the value the height of the largest cylinders tower that can be built, followed by the word "centimeter(s)”.

示例输入

5   
5 3 RED    
4 2 ORANGE   
1 1 GREEN    
3 5 ORANGE    
2 4 BLUE    
3    
10 10 ORANGE    
5 10 GREEN    
6 5 RED    
0

示例输出

15 centimeter(s)    
11 centimeter(s)

我试过用动态规划来解决这个问题，但是给出一个大输入（在限制范围内）的答案需要超过 8 秒；这个解决方案适合这个问题吗？还有其他算法吗？

#include <cstdio>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <string.h>

#define MAX 1000

#define NON -1
#define RED 3
#define ORA 2
#define BLU 1
#define GRE 0

struct cylinder_t{
    int h,r,c;
    cylinder_t():h(0),r(0),c(0){}
    cylinder_t(int height, int radius, int color):h(height),r(radius),c(color){}
};

inline bool compare (const cylinder_t &i,const cylinder_t &j) {
    return i.r > j.r;
}

cylinder_t cylinder[MAX];
inline bool canPut(int i, int last_cylinder_onStack){

    if(last_cylinder_onStack == NON)
        return true;

    if (cylinder[i].r >= cylinder[last_cylinder_onStack].r)
        return false;

    if((cylinder[i].c - cylinder[last_cylinder_onStack].c + 4)%4 == 1)
        return false;

    return true;
}

int memo[MAX][MAX];
int dp(int tower_size, int size, int last_cylinder_onStack){
    if(tower_size == size)
        return 0;

    if(last_cylinder_onStack != NON && memo[tower_size][last_cylinder_onStack] != -1)
        return memo[tower_size][last_cylinder_onStack];

    int maxHeight = 0;
    for (int c = tower_size; c < size; ++c) {
        if(canPut(c, last_cylinder_onStack))
            maxHeight = std::max(maxHeight, cylinder[c].h + dp(tower_size + 1, size, c));
    }

    if(last_cylinder_onStack == NON)
        return maxHeight;
    return memo[tower_size][last_cylinder_onStack] = maxHeight;
}

int main(void){
    //clock_t t;
    //t = clock();

    std::unordered_map<std::string, int> map;
    map["RED"]    = RED;
    map["ORANGE"] = ORA;
    map["GREEN"]  = GRE;
    map["BLUE"]   = BLU;

    int n;
    while(scanf("%d",&n), n != 0){

        for (int i = 0; i < n; ++i) {
            int height,radius;
            char color[15];
            scanf("%d %d %s",&height,&radius,&color[0]);
            cylinder[i].h = height;
            cylinder[i].r = radius;
            cylinder[i].c = map[std::string(color)];
        }

        std::sort(cylinder, cylinder + n, compare);

        memset(memo, -1, sizeof(memo));
        printf("%d centimeter(s)\n",dp(0,n, NON));
    }

    //t = clock() - t;
    //printf("Took %lf seconds to execute \n",((double)t)/CLOCKS_PER_SEC);
}

我在 JAVA 中为这个问题制作了一个 INPUT 生成器：

import java.io.IOException;
import java.util.Random;


public class Main {

    public static void main(String[] args) throws IOException {
        Random r = new Random();
        String color[] = {"RED","ORANGE","GREEN","BLUE"};

        int t = 20;//number of test cases
        for (int i = 0; i < t; i++) {
            int n = r.nextInt(1000) + 1; //number of cylinders
            System.out.println(n);
            for (int j = 0; j < n; j++) {
                System.out.printf("%d %d %s\n",r.nextInt(1000) + 1,r.nextInt(1000) + 1,color[r.nextInt(4)]);
            }
        }

        System.out.println("0");
    }

}

Answer 1

很奇怪你的dp table同时有tower_size和last_cylinder_on_stack参数。我认为 dp 应该只依赖于 last_cylinder_on_stack。在递归函数中，你知道栈上的最后一个柱面，所以你显然应该只从 last_cylinder_on_stack+1

开始循环

所以我认为你应该摆脱 last_cylinder_onStack 参数并将主循环设置为

for (int c = last_cylinder_onStack+1; c < size; ++c) {
    if(canPut(c, last_cylinder_onStack))
        maxHeight = std::max(maxHeight, cylinder[c].h + dp(size, c));
}

构建最大的堆叠塔与集团和限制

Construct biggest stacked tower with blocs and restriction

c++

algorithm

dynamic-programming