小歪和大富翁2.0

解题思路

深度搜索+剪枝。

首先，将n个城市进行划分，得到n/10个城市子序列。由于城市序列是循环的，故而当k > n/10且k % (n/10) > 0 时，会重复遍历前面子序列。所以分类一下，前k % (n/10) 个子序列需要循环 k / (n/10)+1 次，后面子序列的循环次数减一次。

再来看每个长度为10的子序列，首先由于1+2+3+4=10，从起点0出发，一定会到达终点10，但3个中间城市的组合是不确定的，总共有4！=24种组合方式。

那么可以将问题转换一下，若需要循环遍历子序列m次，相当于从24个集合里选取m个（允许重复选取），使其m个集合的并集的元素和最大化。为了兼容重复选取，问题可以转化为选取的集合数量不超过m个。

那么现在寻找单个子序列上的最大值，就变成了一个常规的搜索问题，纯粹暴力搜索的复杂度为24!。但是由于最多会有10000个子序列，每次完全的暴力搜索必然超时，故而需要剪枝，剪枝策略为如果再次发现已经被找到的并集，则跳出该分支。

代码展示

实现代码上做了一些特殊处理，例如使用回溯法生成24种排列组合，实际上也可以直接人工列出。

对于3个中间城市，由于其序号始终位于1-9之间，我选择使用整数mask来表示集合，第i个比特位为1表示第i个城市处于该集合，这样可以直接用位运算求并集，也便于记录搜索的状态。

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int[][] paths = new int[24][4];
    static int[] masks = new int[24];
    static int index = 0;
    static long[] max_gains = new long[26];
    static int max_depth = 0;
    static boolean[] visited = new boolean[1024];

    // 回溯法生成24种组合
    private static void backTrace( int[] current, int cnt, boolean[] used){
        if(cnt==4) {
            for(int j=0; j<4; j++){
                paths[index][j] = current[j];
            }
            index ++;
        }
        for(int i=0; i<4; i++){
            if(used[i]){
                continue;
            } else {

                current[cnt] = i+1;
                used[i] = true;
                backTrace(current, cnt + 1, used);
                used[i] = false;
            }
        }
    }

    // 深度搜索
    private static void dfs(int[] money, int mask, long cur_gain, int cur_index, int depth){
        if(depth >= max_depth) return;
        int chosen_mask = masks[cur_index];
        int new_mask = chosen_mask | mask;
        if(!visited[new_mask]){
            visited[new_mask] = true;
            int op = 1;
            long new_gain = 0;
            for(int i=0; i<9; i++){
                if((op & new_mask) > 0){
                    new_gain += money[i];
                }
                op = op << 1;
            }

            max_gains[depth+1] = Math.max(max_gains[depth+1],new_gain);

            for(int j=cur_index + 1; j<24; j++){
                dfs(money, new_mask, new_gain, j, depth+1);
            }

        }
        return;

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int stage_num = n / 10;
        int[][] arr = new int[stage_num][10];
        arr[stage_num-1][9] = in.nextInt();
        for(int i=0; i<stage_num-1; i++){
            for(int j=0; j<10; j++)
                arr[i][j] = in.nextInt();
        }
        for(int j=0; j<9; j++){
            arr[stage_num-1][j] = in.nextInt();
        }
        int[] current = new int[4];
        boolean[] used = new boolean[4];
        backTrace(current, 0, used);
        for(int i=0; i<24; i++){
            int cur_index = 0;
            int mask = 0;
            for(int j=0; j<3; j++){
                cur_index += paths[i][j];
                mask |= 1 << (cur_index-1);
            }
            masks[i] = mask;
        }

        long res = 0;

        int mid = 0;
        if(k % stage_num == 0){
            max_depth = k / stage_num;
            mid = stage_num;
        } else {
            max_depth = k / stage_num + 1;
            mid = k % stage_num;
        }
        max_depth = Math.min(25, max_depth);

        long min_inf = -0x7fffffffffffffffL-1;
        for(int i=0; i<stage_num; i++){
            if(i==mid) max_depth -= 1;
            if(max_depth <= 0) continue;
            for(int j=0; j<1024; j++){
                    visited[j] = false;
            }
            for(int j=0; j<=max_depth ; j++){
                max_gains[j] = min_inf;
            }
            for(int j=0; j<24; j++){
                dfs(arr[i], 0, min_inf, j, 0);
            }
            long stage_max_gain = min_inf;
            for(int j=1; j<=max_depth; j++){
                stage_max_gain = Math.max(stage_max_gain, max_gains[j]);
            }
            res += stage_max_gain + arr[i][9];
        }

        System.out.print(res);
    }
}