ccf java高速公路,CCF201809

高速公路,CCF201809"/>

ccf java高速公路,CCF201809

dfs(int cur, int last, int s, int e, int[] path)

/**

* 计算从cur位置开始，上一位是last,当前位置可选范围从s~e的结果

* 若当前状态不成立，加入set保存这一结果，以免下次在遇到这个状态还要重新计算

* @param cur 当前需填写的位置

* @param last 上一位的数字

* @param s 从s开始选

* @param e 最大选到e

* @param path 保存路径

* @return 当前状态不成立，返回false，成立返回true

*/

暴力递归

记忆化搜索

此题目中需要推导的公式(一般状态)

起点状态

(有时会出现负数)

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.HashSet;

import java.util.Set;

public class Main {

static int N = 305, n;

static int a[] = new int[N];

static Set set = new HashSet();//状态保存

static BufferedWriter bw;

public static void main(String[] args) throws NumberFormatException, IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

bw = new BufferedWriter(new OutputStreamWriter(System.out));//优化输入输出

n = Integer.parseInt(br.readLine());

String[] s = br.readLine().split(" ");

for (int i = 1; i <= n; i++)a[i] = Integer.parseInt(s[i-1]);

int path[] = new int[N];

dfs(1, 0, 1, 0, path);

bw.flush();

}

private static boolean dfs(int cur, int last, int s, int e, int[] path) throws IOException {

if(set.contains(cur+"-"+last+"-"+s+"-"+e)) return false;

if (cur == 1) {

for (int i = s;; i++) {

path[1] = i;

if (dfs(2, i, Math.max(2 * a[1] - i, 1), 2 * a[1] + 1 - i, path))return true;

}

} else if (cur != n) {

for (int i = s; i <= e; i++) {

if ((last + i + 1) / 3 > a[cur]) {//数字选择的过大

set.add(cur+"-"+last+"-"+s+"-"+e);

return false;

}

path[cur] = i;

if (dfs(cur + 1, i, Math.max(3 * a[cur] - (last + i), 1), 3 * a[cur] + 2 - (last + i), path))return true;

}

} else {

for (int i = s; i <= e; i++) {

if ((last + i) >> 1 > a[cur]) {//数字过大

set.add(cur+"-"+last+"-"+s+"-"+e);

return false;

}

if ((last + i) >> 1 == a[cur]) {

path[cur] = i;

for (int k = 1; k <= n; k++)

bw.write(path[k] + " ");

return true;

}

}

}

set.add(cur+"-"+last+"-"+s+"-"+e);

return false;

}

}