arius1408's blog

By arius1408, history, 7 months ago, In English

Recently I've been doing this USACO problem. After a while I came up with a simple idea. I'll have dp[i][j] as the maximum result from the i-th element to the j-th element, calculate each range in increasing order. If there are two subarrays [L, X] and [X+1, R] and dp[L][X] equal to dp[X+1][R], then result for dp[L][R] is dp[L][X]+1, else I will just take max(dp[L][X], dp[X+1][R]) as an answer. This seem right to me as I tested it against some small cases. But there are 12 tests in total, and I have those WAs from test (7 -> 12). The expected answer is always smaller than my output, for example, if the true answer is X, then my code output X+1. Those test case is just to large for me to check (N = 248) so I'm here asking for help. Why am I wrong ? Which mistake did I make ?

Below is my code for this problem :

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

const int N = 248;
int n, a[N], dp[N][N];

int32_t main () {
	freopen("248.out", "w", stdout);
	freopen("248.in", "r", stdin);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for (int i = 0; i < n; i++) cin>>a[i];
	for (int i = 0; i < n; i++) dp[i][i] = a[i];
	for (int len = 2; len <= n; len++) {
		for (int i = 0; i < n; i++) {
			int j = i+len-1;
			if (j >= n) break;
			for (int k = i; k < j; k++) {
				int cur_ans = max(dp[i][k], dp[k+1][j]);
				if (dp[i][k] == dp[k+1][j]) cur_ans++;
				dp[i][j] = max(dp[i][j], cur_ans);
			}
		}
	}
	cout<<dp[0][n-1];
}

And here is the jury code (Java) for this problem :

import java.io.*;
import java.util.*;
public class two48 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("248.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("248.out")));
		int n = Integer.parseInt(br.readLine());
		int[] list = new int[n];
		for(int i = 0; i < n; i++) {
			list[i] = Integer.parseInt(br.readLine());
		}
		int[][] dp = new int[n][n];
		int ret = 0;
		for(int len = 1; len <= n; len++) {
			for(int i = 0; i + len <= n; i++) {
				int j = i+len-1;
				dp[i][j] = -1;
				if(len == 1) {
					dp[i][j] = list[i];
				}
				for(int k = i; k < j; k++) {
					if(dp[i][k] == dp[k+1][j] && dp[i][k] > 0) {
						dp[i][j] = Math.max(dp[i][j], dp[i][k] + 1);
					}
				}
				ret = Math.max(ret, dp[i][j]);
			}
		}
		pw.println(ret);
		pw.close();
	}
}

Now, I think I understand the jury idea for this problem (al least I think so, look pretty much the same as mine). But the is something that bugged me though ... In all of the accepted codes I've read of this problem, they always aim to get a maximum answer (a separate variable named ret in the jury code), while I'm trying to help an optimal answer by dp[0][N-1] (DP result of the whole array). There're some other difference like a small detail about how they calculate dp[i][j] though. I can't see the actual difference. Pls kindly point out where did I screw up ...

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
7 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Weird ... There are upvotes, but there is no answer. Normally there're lots of downvotes on my blog, but there're answers too, which is what I need to improve.

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

As I understand in the third for ,if the maxima of the ranges [i-k] and [k+1,j] are equal they add one (remember that you can do this if and only if they are adjacent). Example: 4 2 4 The answer is 4 , but according to your program 5 since it oviates 2 . You should keep in mind what number your DP ends and begins on. https://www.youtube.com/watch?v=OdHxOYICx-o