top of page

2016 S4: Combining Riceballs

This is a dynamic programming question.

Suppose f(i, j) express if it can be combined from the ith rice ball to the jth rice ball. combine(i, j) is the sum from the ith rice ball to jth rice ball. raw[N] is an array that is each rice ball weight.

f(i, j) = true means it can combine from i to j. Otherwise, it is false.

1. if i = j , f(i, j) = true, combin(, i, j) = raw[i]

2. if j = i+1 and raw[i] = raw[j], f(i, j) = true, combine = raw[i] + raw[j]

3. if j = i+2, raw[i] = raw[j], f(i, j) = true, combine = raw[i] + raw[i+1]+raw[j]

4. if j - i > 2, then:

case 1, if f(i, k) and f(k+1, j) are true, and combine(i, k) = combine(k+1, j), f(i,j) is true.

case 2: if f(i, k), f(k+1, m), f(m+1, j) are true, and combine(i, k) = combine(m+1, j), f(i, j) is true.

combine(i, j) are the sum of raw[i] to raw[j]

C++ code, f(i, j) and combine(i, j) can be same array, if f(i,j) = 0, means not combin, more than 0, can be combine.


#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;

}



Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Comentarios


bottom of page