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;
}
Comentários