USACO 2016 US Open Contest, Gold Problem 3. 248

Category: 计算机国际竞赛 Date: 2017年11月8日下午9:40

原题下载：

USACO2016-OPEN-G3

答案：
Here is my Java solution.

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();
}
}