title: Tiling a 2xM array with 2x1 tiles to maximise the differences - INOI 2008, P2
body: <p>(As I am new and may not be aware of the code of conduct, feel free to edit this post to make this better and more helpful to other people.)</p>
  <p>Greetings everybody!</p>
  <p>This problem is related to this: <a href="https://www.iarcs.org.in/inoi/2008/inoi2008/inoi2008-qpaper.pdf" rel="nofollow noreferrer">Problem Link</a></p>
  <blockquote>
  <p>The problem <strong>in brief</strong>:</p>
  <p>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 &quot;covered&quot; via the individual tiles is maximized. We want to report this max sum.</p>
  <p>The problem <strong>in detail</strong>:</p>
  <p>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.</p>
  </blockquote>
  <p>Below is my code for it. Basically, I've done a sort of a recursive thing because there are two cases: (1) One vertical 2x1 tile in the start and (2) Two horizontal 2x1 laid together to cover 2 columns.</p>
  <pre><code>#include &lt;bits/stdc++.h&gt;
  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 &gt;&gt; N;
      int array[N][2]; for(int i=0;i&lt;N;i++) cin &gt;&gt; array[i][0] &gt;&gt; array[i][1]; 
  
      cout &lt;&lt; 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);
  }
  </code></pre>
  <p>However, this seems to be a very inefficient solution and I can't really understand how to cover the base cases (otherwise this would go on forever).</p>
  <p>Any help would be really appreciated. Thank You! (BTW I want to create a new tag - Competitive Programming, can anybody help me do so?)</p>