Lazy Cows (http://poj.org/problem?id=2430)
import java.util.*; | |
import java.io.*; | |
public class Main { | |
/************************ SOLUTION STARTS HERE ************************/ | |
static final int INF = (int) 1e9; | |
private static void solve() { | |
int N = nextInt(); | |
int K = nextInt(); | |
int B = nextInt(); | |
int arr[][] = new int[N][]; | |
for(int i = 0; i < N; i++) | |
arr[i] = nextIntArray(2); | |
// Sorts the entries in ascending order of columns and breaking ties with row | |
Arrays.sort(arr , new Comparator<int[]>() { | |
@Override | |
public int compare(int[] o1, int[] o2) { | |
if(o1[1] != o2[1]) | |
return o1[1] - o2[1]; | |
else | |
return o1[0] - o2[0]; | |
} | |
}); | |
int sz = 1; | |
for(int i = 1; i < N; i++) | |
sz += arr[i][1] != arr[i - 1][1] ? 1 : 0; | |
/* | |
The compress array stores one entry for each column | |
compress[i][0] = ith smallest column | |
compress[i][1] = 0 - only up , 1 - only down , 2 - both | |
*/ | |
int compress[][] = new int[sz][2]; | |
int ptr = 0; | |
for(int i = 0; i < N; ) { | |
compress[ptr][0] = arr[i][1]; | |
if(i + 1 < N && arr[i][1] == arr[i + 1][1]) { | |
compress[ptr++][1] = 2; | |
i += 2; | |
} else { | |
compress[ptr++][1] = arr[i][0] - 1; | |
i++; | |
} | |
} | |
int[][] costH1 = new int[sz][sz]; // one horizontal rect ---- | |
int[][] costH2 = new int[sz][sz]; // two horizontal rect ==== | |
int[][] costV = new int[sz][sz]; // one vertical rect | | | |
for(int i = 0; i < sz; i++) { | |
int firstUp = 0 , firstDown = 0; | |
int lastUp = -1 , lastDown = -1; | |
costH1[i][i] = compress[i][1] == 2 ? INF : 1; | |
costH2[i][i] = compress[i][1] == 2 ? 2 : INF; | |
costV[i][i] = 2; | |
int first = compress[i][1]; | |
boolean flag = compress[i][1] != 2; | |
if(compress[i][1] != 1) | |
firstUp = lastUp = compress[i][0]; | |
if(compress[i][1] != 0) | |
firstDown = lastDown = compress[i][0]; | |
for(int j = i + 1; j < sz; j++) { | |
costV[i][j] = 2 * (compress[j][0] - compress[i][0] + 1); | |
flag &= compress[j][1] == first; | |
costH1[i][j] = flag ? compress[j][0] - compress[i][0] + 1 : INF; | |
if(firstUp == 0 && compress[j][1] != 1) | |
firstUp = lastUp = compress[j][0]; | |
if(firstDown == 0 && compress[j][1] != 0) | |
firstDown = lastDown = compress[j][0]; | |
lastUp = compress[j][1] != 1 ? compress[j][0] : lastUp; | |
lastDown = compress[j][1] != 0 ? compress[j][0] : lastDown; | |
costH2[i][j] = flag ? INF : (lastUp - firstUp + 1) + (lastDown - firstDown + 1); | |
} | |
} | |
int DP[][] = new int[K + 1][sz]; | |
Arrays.fill(DP[0], INF); | |
for(int i = 0; i < sz; i++) | |
DP[1][i] = Math.min(costV[0][i] , costH1[0][i]); | |
for(int i = 2; i <= K; i++) { | |
for(int j = 0; j < sz; j++) { | |
DP[i][j] = INF; | |
for(int k = -1; k < j; k++) { | |
int dp1 = k == -1 ? 0 : DP[i - 1][k]; | |
int dp2 = k == -1 ? 0 : DP[i - 2][k]; | |
DP[i][j] = Math.min(DP[i][j] , dp1 + Math.min(costV[k + 1][j] , costH1[k + 1][j])); | |
DP[i][j] = Math.min(DP[i][j] , dp2 + costH2[k + 1][j]); | |
} | |
} | |
} | |
println(DP[K][sz - 1]); | |
} | |
/************************ SOLUTION ENDS HERE ************************/ | |
/************************ TEMPLATE STARTS HERE **********************/ | |
public static void main(String[] args) throws IOException { | |
reader = new BufferedReader(new InputStreamReader(System.in)); | |
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false); | |
st = null; | |
solve(); | |
reader.close(); | |
writer.close(); | |
} | |
static BufferedReader reader; | |
static PrintWriter writer; | |
static StringTokenizer st; | |
static String next() | |
{while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;} | |
st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();} | |
static String nextLine() {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;} | |
static int nextInt() {return Integer.parseInt(next());} | |
static long nextLong() {return Long.parseLong(next());} | |
static double nextDouble(){return Double.parseDouble(next());} | |
static char nextChar() {return next().charAt(0);} | |
static int[] nextIntArray(int n) {int[] a= new int[n]; int i=0;while(i<n){a[i++]=nextInt();} return a;} | |
static long[] nextLongArray(int n) {long[]a= new long[n]; int i=0;while(i<n){a[i++]=nextLong();} return a;} | |
static int[] nextIntArrayOneBased(int n) {int[] a= new int[n+1]; int i=1;while(i<=n){a[i++]=nextInt();} return a;} | |
static long[] nextLongArrayOneBased(int n){long[]a= new long[n+1];int i=1;while(i<=n){a[i++]=nextLong();}return a;} | |
static void print(Object o) { writer.print(o); } | |
static void println(Object o){ writer.println(o);} | |
/************************ TEMPLATE ENDS HERE ************************/ | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment