OJ Board

Code: Select all

// Winterim Backpacking Trip
// UVA : 907

#include <stdio.h>
#include <string.h>

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

const int NN = 601;
const int MAXK = 301;

int sum[NN];
int dist[NN];

void init(int n) {
  sum[0] = dist[0];
  for (int i = 1; i <= n; i++)
    sum[i] = sum[i-1] + dist[i];
}

int memo[NN][NN][MAXK];

int go(int i, int j, int k) {
  if (memo[i][j][k] != -1) return memo[i][j][k];

  int& ret = memo[i][j][k];

  if (k == 0) {
    ret = sum[j];
    if (i)
      ret -= sum[i-1];
    return ret;
  }

  if (i == j) {
    ret = dist[i];
    return ret;
  }
  
  if (i > j) {
    ret = (1<<30);
    return ret;
  }
  
  ret = max(go(i + 1, j, k-1), dist[i]);
  ret = min(ret, max(go(i, j-1, k-1), dist[j]));
  ret = min(ret, max(dist[i] ,dist[j]) + go(i + 1, j - 1, k));

  return ret;
}

int main() {
  int n, k;

  while (scanf("%d %d", &n, &k) == 2) {
    for (int i = 0; i <= n; i++) 
      scanf("%d", &dist[i]);
    
    init(n);
    memset(memo, -1, sizeof(memo));

    if (k > n + 1)
      k = n + 1;
    printf("%d\n", go(0, n, k));
  }

  return 0;
}

Code: Select all

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static int table[][];
	static int a[];
	static int b[];
	static int sum[][];

	public static void main(String args[])throws IOException {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int N = sc.nextInt();
			int K = sc.nextInt();
			a = new int[N + 1];
			b = new int[N + 1];
			for(int i = 0; i < (N + 1); i ++) {
				a[i] = sc.nextInt();
			}
			sum = new int[N + 1][N + 1];
			table = new int[N + 1][K + 1];
			for (int i = 0; i < (N + 1); i ++) {
				for(int j = 0; j < (K + 1); j ++) {
					table[i][j] = -1;
				}
			}
			for(int i = N; i >= 0; i --) {
				b[i] = a[N - i];
			}
			for(int i = 0; i < N + 1; i ++) {
				int sum = 0;
				for(int j = 0; j <= i; j ++) {
					sum = sum + b[j]; 
				}
				table[i][0] = sum;
			}
			for(int i = 1; i < (K + 1); i ++) {
				table[0][i] = b[0];
			}
			for(int i = 0; i < (N + 1); i ++) {
				for(int j = i - 1; j >= 0; j --) {
					int s = 0;
					for(int k = i; k > j; k --) {
						s = s + b[k];
					}
					sum[i][j] = s;
				}
			}
			System.out.println(DP(N, K));
		}
	}

	public static int DP(int n, int k) {
		if (table[n][k] != -1)
			return table[n][k];
		else {
			int min = Integer.MAX_VALUE/2;
			for(int i = n - 1; i >= 0; i --) {
				int temp = Math.max(sum[n][i], DP(i, k - 1));
				if(temp < min)
					min = temp;
			}
			table[n][k] = min;
			return table[n][k];
		}
	}
}