CCF201809-4 再卖菜（JAVA ）好像通过这道题悟到了

      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
     */
    

• 暴力递归
• 记忆化搜索

此题目中需要推导的公式（一般状态）

起点状态

1. (有时会出现负数)
2. 

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<String> set = new HashSet<String>();//状态保存
    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;
    }
}