CCC '16 S4 - Combining Riceballs

https://www.cemc.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf

Solution 1:

recursive that is based on DP solution, please read DP notes:

#include <iostream>
#include <string.h>
using namespace std;
int n;
int sum[402];
int ans;
bool riceball_recur(int left, int right){
   if(left == right){
      ans = left > 0 ? max(ans, sum[right] - sum[left-1]):max(ans, sum[right]);
      return true;
   }
   if(right < left){
      return true;
   }
   int len = right - left + 1;
   for(int gap = 0; gap < len; gap++){

      for(int left_len = 0; left_len < len; left_len++){
         int leftend =left + left_len;
            int rightstart = leftend + gap + 1;
            if(rightstart > right){
               break;
            }
            else{
               int gapstart = leftend+1;
               int gapend = rightstart - 1;

               if(riceball_recur(left, leftend) &&
                  riceball_recur(gapstart, gapend) &&
                  riceball_recur(rightstart, right)){
                  int leftball =  left > 0?(sum[leftend] - sum[left-1]):sum[leftend];
                  int rightball = sum[right] - sum[rightstart-1];
                  if(leftball == rightball){
                     ans = left > 0 ? max(ans, sum[right] - sum[left-1]):max(ans, sum[right]);
                     return true;
                  }
               }
            }
      }
   }
   return false;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int c;
        cin >> c;
        ans = max(ans, c);
        if (!i)
           sum[0]=c;
        else
           sum[i]=sum[i-1]+c;
    }
    riceball_recur(0, n-1);
    cout << ans;
    return 0;
}

Solution 2:

DP[i, j] is true if i to j can be merge, otherwise is false.

if i == j,

DP[i, j] = true and sum[i,j] and update max riceball.

else if j - i + 1 ==2 and raw[i] == raw[j]:

DP[i, j] = true and sum[i,j] and update max riceball .

else:

int left, right; i <= left< right<=j

if DP[i, left ] == true and DP[right, j] == true and DP[left+1, right-1] == true

and sum[i,left] == sum[right,j]

DP[i,j] = true and update max riceball

#include <iostream>
#include <string.h>
using namespace std;
int n;
int dp[402][402] = {0};
int sum[402];
int ans;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> dp[i][i];
        ans = max(ans, dp[i][i]);
        if (!i)
           sum[0]=dp[i][i];
        else
           sum[i]=sum[i-1]+dp[i][i];
    }
    for (int len = 1; len < n; len++)
    {
        for (int l = 0; l < n-len; l++)
        {
            int r = l+len;
            int j = l+1;
            int k = r;
            while(j<=k)
            {
                if (dp[l][j-1]&&
                    dp[l][j-1]==dp[k][r]&&
                    (j==k||dp[j][k-1]))
                {
                    dp[l][r]=max(dp[l][r],dp[l][j-1]+
                                 dp[j][k-1]+dp[k][r]);
                    ans=max(ans,dp[l][r]);
                    break;
                }
                if (sum[j-1]-sum[l-1]<sum[r]-sum[k-1])
                   j++;
                else
                   k--;
            }
        }
    }
    cout << ans;
    return 0;
}