解题思路

深度搜索+剪枝。

首先，将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);     } }