腾讯编程题第一个

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

while (scan.hasNext()) {

int n = scan.nextInt();

int k = scan.nextInt();

int[][] a = new int[n][n];

for (int i = 0; i < n; i++) {

String str = scan.next();

char[] c = str.toCharArray();

for (int j = 0; j < c.length; j++) {

a[i][j] = c[j] - '0';

}

}

double[][] dp = new double[n][k + 1];

for (int i = 0; i < dp.length; i++) {

for (int j = 0; j < dp[i].length; j++) {

dp[i][j] = Integer.MAX_VALUE;

}

}

dp[2][0] = a[0][2];

if (k > 0)

dp[2][1] = a[0][2] / 2.0;

for (int i = 3; i < dp.length; i++) {

for (int j = 0; j <= k; j++) {

if (j == 0)

dp[i][j] = Math.min(dp[i - 1][0] + a[i - 1][i], a[0][i]);

else if (j == 1)

dp[i][j] = Math.min(a[0][i] / 2.0,

Math.min(dp[i - 1][j - 1] + a[i - 1][i] / 2.0, dp[i - 1][j] + a[i - 1][i]));

else

dp[i][j] = Math.min(dp[i - 1][j - 1] + a[i - 1][i] / 2.0, dp[i - 1][j] + a[i - 1][i]);

}

}

// for (int i = 0; i < dp.length; i++) {

// for (int j = 0; j < dp[i].length; j++) {

// System.out.print(dp[i][j]+" ");

// }

// System.out.println();

// }

double res = Integer.MAX_VALUE;

for (int i = 2; i < dp.length; i++) {

for (int j = 0; j <= k; j++) {

double x = dp[i][j] + a[i][1];

if (j == 0) {

res = Math.min(x, res);

continue;

}

double y = dp[i][j - 1] + a[i][1] / 2.0;

res = Math.min(res, Math.min(x, y));

}

}

if (k == 0)

System.out.println(Math.min(res, a[0][1]));

else

System.out.println(Math.min(res, a[0][1] / 2.0));

}

}

}