c++ - 用 2x1 block 平铺 2xM 阵列以最大化差异 - INOI 2008，P2

Question

(由于我是新人，可能不了解行为准则，请随时编辑这篇文章，使其变得更好，对其他人更有帮助。)

大家好!

此问题与此相关:Problem Link

The problem in brief:

Given a 2xM array and we want to tile it with 2x1 tiles such that the sum of absolute values of the differences of the values "covered" via the individual tiles is maximized. We want to report this max sum.

The problem in detail:

In Domino Solitaire, you have a grid with two rows and many columns. Each square in the grid contains an integer. You are given a supply of rectangular 2×1 tiles, each of which exactly covers two adjacent squares of the grid. You have to place tiles to cover all the squares in the grid such that each tile covers two squares and no pair of tiles overlap. The score for a tile is the difference between the bigger and the smaller number that are covered by the tile. The aim of the game is to maximize the sum of the scores of all the tiles.

下面是我的代码。基本上，我做了一种递归的事情，因为有两种情况:(1) 开始时有一个垂直的 2x1 平铺，(2) 两个水平的 2x1 平铺在一起以覆盖 2 列。

#include <bits/stdc++.h>
using namespace std;

int maxScore(int array[][2], int N, int i);

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int array[N][2]; for(int i=0;i<N;i++) cin >> array[i][0] >> array[i][1]; 

    cout << maxScore(array, N, 0);

    return 0;
}

int maxScore(int array[][2], int N, int i){
    int score1 = abs(array[i][0] - array[i][1]) + maxScore(array, N, i+1);
    int score2 = abs(array[i][0] - array[i+1][0]) + abs(array[i][1] - array[i+1][1]) + maxScore(array, N, i+2);
    return max(score1, score2);
}

但是，这似乎是一个非常低效的解决方案，我无法真正理解如何覆盖基本情况(否则这将永远持续下去)。

任何帮助将不胜感激。谢谢你! (顺便说一句，我想创建一个新标签 - 竞争性编程，有人可以帮助我吗？)

Answer 1

维护一个最佳解决方案数组，其中数组第 i 列中的值是仅考虑输入矩阵的匹配列的最佳解决方案。然后，通过向 arr[i-1] 解决方案添加 1 个图 block 或向 arr[i-2] 解决方案添加 2 个图 block ，arr[i] = max 可能。将 arr[-1] 视为 0，并将 arr[0] 设置为一个垂直多米诺骨牌的 val。