## Friday, May 22, 2015

### ROCK. SPOJ - ROCK solution

Problem: www.spoj.com/problems/ROCK

Source (Java), AC:

```import java.io.*;

class ROCK {

public static int[] data;
public static int[][] dp;

public static int solve(int from, int to) {
int ones = 0, zeros = 0;

if(from>to)return 0;
if (dp[from][to] != -1) return dp[from][to];

for (int i = from; i <= to; ++i) {
if (data[i] == 1) ones++;
else zeros++;
}

if(ones>zeros)return dp[from][to]=ones+zeros;

if(from==to) return data[to];
int max = 0;

for(int i=from;i<=to;++i){
int left = 0;
if(i!=to)left = solve(from, i);
int right = 0;
if(i+1!=from)right = solve(i+1, to);
if(left+right>max){max = left+right;}
}
return dp[from][to] = max;
}

public static void main(String[] args) throws Exception {
int nCases = IO.nextInt();
while (nCases-- > 0) {
int length = IO.nextInt();
data = IO.nextIntArray(length, "");
dp = new int[length + 1][length + 1];
for (int i = 0; i < length + 1; ++i) {
for (int j = 0; j < length + 1; ++j) {
dp[i][j] = -1;
}
}
IO.println(solve(1, length));
}
}
```
```    static class IO {

public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
int[][] arr = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; ++i) {
arr[i] = nextIntArray(cols, seperator);
}
return arr;
}

public static int[] nextIntArray(int nInts, String seperator) throws IOException {
String ints = br.readLine();
String[] sArray = ints.split(seperator);
int[] array = new int[nInts + 1];
for (int i = 1; i <= nInts; ++i) {
array[i] = Integer.parseInt(sArray[i - 1]);
}
return array;
}

public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
String longs = br.readLine();
String[] sArray = longs.split(seperator);
long[] array = new long[nLongs + 1];
for (int i = 1; i <= nLongs; ++i) {
array[i] = Long.parseLong(sArray[i - 1]);
}
return array;
}

public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
String doubles = br.readLine();
String[] sArray = doubles.split(seperator);
double[] array = new double[nDoubles + 1];
for (int i = 1; i <= nDoubles; ++i) {
array[i] = Double.parseDouble(sArray[i - 1]);
}
return array;
}

public static char[] nextCharArray(int nChars, String seperator) throws IOException {
String chars = br.readLine();
String[] sArray = chars.split(seperator);
char[] array = new char[nChars + 1];
for (int i = 1; i <= nChars; ++i) {
array[i] = sArray[i - 1].charAt(0);
}
return array;
}

public static int nextInt() throws IOException {
String in = br.readLine();
return Integer.parseInt(in);
}

public static double nextDouble() throws IOException {
String in = br.readLine();
return Double.parseDouble(in);
}

public static long nextLong() throws IOException {
String in = br.readLine();
return Long.parseLong(in);
}

public static int nextChar() throws IOException {
String in = br.readLine();
return in.charAt(0);
}

public static String nextString() throws IOException {
}

public static void print(Object... o) {
for (Object os : o) {
System.out.print(os);
}
}

public static void println(Object... o) {
for (Object os : o) {
System.out.print(os);
}
System.out.print("\n");
}

public static void printlnSeperate(String seperator, Object... o) {
StringBuilder sb = new StringBuilder();
sb.delete(sb.length() - seperator.length(), sb.length());
System.out.println(sb);
}
}
}```