旅游网站首页设计大概图,桂林两江四湖游船路线,做网站卖大闸蟹,超星毕业设计平台AcWing 1068. 环形石子合并
题意#xff1a;
n堆石头围成一个圈#xff0c;然后将相邻两堆合并成新的一堆#xff0c;得分为新的一堆的石头数 问最高得分合最低得分
题解#xff1a;
很简单#xff0c;区间dp的模板题 和这个题一样 状态转移方程#xff1a; dpmax[i]…AcWing 1068. 环形石子合并
题意
n堆石头围成一个圈然后将相邻两堆合并成新的一堆得分为新的一堆的石头数 问最高得分合最低得分
题解
很简单区间dp的模板题 和这个题一样 状态转移方程 dpmax[i][j] max(dp[i][k]dp[k1][j]sum[j]-sum[i-1]) dpmin[i][j]min(dp[i][k]dp[k1][j])sum[j]-sum[i-1] 因为题目说的是环形所以数组复制一倍 马上要java期末考试所以用java练练
代码
import java.io.*;
import java.util.*;class Main{static BufferedReader read new BufferedReader(new InputStreamReader(System.in));static int N 410, INF 0X3f3f3f3f;static int[] a new int[N], sum new int[N];static int[][] dpMax new int[N][N];static int[][] dpMin new int[N][N];public static void main(String[] args) throws Exception{int n Integer.valueOf(read.readLine());String[] ss read.readLine().split( );for(int i 1; i ss.length; i){a[i] Integer.valueOf(ss[i - 1]);a[i n] Integer.valueOf(ss[i - 1]);}for(int i 1; i 2 * n; i){sum[i] sum[i - 1] a[i];Arrays.fill(dpMax[i], -INF);Arrays.fill(dpMin[i], INF);}for(int len 1; len n; len){for(int i 1; i len - 1 2 * n; i){int j i len - 1;if(len 1) {dpMax[i][j] dpMin[i][j] 0;}else{for(int k i; k j; k){dpMax[i][j] Math.max(dpMax[i][j], dpMax[i][k] dpMax[k 1][j] sum[j] - sum[i - 1]);dpMin[i][j] Math.min(dpMin[i][j], dpMin[i][k] dpMin[k 1][j] sum[j] - sum[i - 1]);}}}}int max -INF, min INF;for(int left 1; left n; left){max Math.max(max, dpMax[left][left n - 1]);min Math.min(min, dpMin[left][left n - 1]);}System.out.println(min);System.out.println(max);}}
