平凡


私信TA

用户名:uq_30153938431

访问量:3593

签 名:

等  级
排  名 1109
经  验 2258
参赛次数 0
文章发表 13
年  龄 20
在职情况 学生
学  校 广西建设职业技术学院
专  业 网络技术

  自我简介:

啥时候我能升本....

TA的其他文章

解题思路:

    其实这道题目相对来说,比较容易。为啥呢?因为,很容易就能分析出它的最优子结构。很容易就能根据最优子结构得到子问题。这里我就来分析一下这个问题的最优子结构吧。

    最优子结构:

        为了方便研究,我把每一个珠子加上编号Ai(0<=i<=N)。珠子是两个两个的释放能量,释放完能量后又合成了一个,可以这样理解。比如:A1=(1,2) A2=(2,3) A3=(3,1)  (A1◎A2)释放之后就 = (1,3)接着与A3结合再释放。它的问题是让我们算出所有珠子最大可以释放多少能量。这个时候我们可以把随便拿一个很小的问题来试试,比如N=1的时候,这个不释放,因为只有一个。N=2的时候,能释放但只有一种组合。

        N = 3的时候,能量链A1 A2 A3,而且是成圆圈的。这个时候,就有三个组合了, (A1◎A2)◎A3 / (A1◎A3)◎A2 / A1◎(A2◎A3)。那我们是怎么分的呢,就是先算两个珠子的,在两个珠子的基础上再加上一个。如果是四个呢,那就算三个珠子,再加上一个珠子就是四个珠子的。这里我们可以描述成分成两份,两份再分...。比如:N=3的时候,分两份是不是只有2个珠子和1一个珠子两种,但是有三种组合。是不是可以从A1 A2 A3中间分,然后只需要找到两份的最优解再相加就得到最后的最优解了。这里就是一个最优子结构了,这里的两份最优解是再同一个位置上的最优解,怎么解释呢....,就是(A1◎A2)◎A3分成了 A1◎A2/A3两份,然后求出左边这份的最优解,右边这份的最优解。合起来就是最优解了。这里看不出来,因为左边是两个珠子,一种组合,右边是一个能量直接=0。

    子问题:

        由最优子结构得到,我们的子问题是份。一开始把珠子分成两份,两份再分,一直分到每一份只有两个或一个珠子的时候就没必要再分了。我们引入一个k,就是代表在哪里分。

        我们再引入一个数组m[i,j],i代表起点,j代表终点,m[i,j]就是能量和。就比如(A1◎A2)◎A3 可以描述成m[1,3] = m[1,2]+m[3,3] + 新的珠子能量。这里m[1,2]就是A1◎A2释放的能量,m[3,3]就是A3释放的能量(其实=0),新的珠子能量就是A1◎A2组成的新珠子再和A3释放的能量。这里还要解释一下:为什么A1◎A2可以组成新的珠子...,题目信息,比如 A1=(1,2) A2=(2,3) A3=(3,1) ,A1◎A2之后就得到新的(1,3)了...,然后再和A3结合。

        所有得到那个表达式:m[i,j] = m[i,k] + m[k+1,j] + 新的能量

        但是嘞,注意这里是组成一个圆形:那个A1 A2 A3 中每一个相邻部分都可以组合。A1◎A2 / A2◎A3 / A3◎A1 就是这里。

        所以得到新的表达式:m[i,j] = m[i,k%N] + m[(k+1)%N,j] + 新的能量


这个新的能量我直接封装到一个方法里面了,这个就是看规律得到的。

这是最终的:dp[i][j] = Math.max(dp[i][j], dp[i][k%n] + dp[(k+1)%n][j] + p(i,(k+1)%n,(j+1)%n));

public static int p(int i,int k,int j) {   

  return arrays[i]*arrays[k]*arrays[j];
}

说实话,真的不知道怎么解释,我还是举例子吧:A1=(1,2) A2=(2,3) A3=(3,1)这个数据的输入是 N = 3, 1 2 3

(A1◎A2)◎A3  A1◎A2得到新的(1,3)  再和A3(3,1)结合=1*3*1,起点 是A1,分点是A2,终点是A3,i=1,k=2,j=3。哎....点到这里了...




参考代码:

static int arrays[] = null;
public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  int n = scanner.nextInt();
  arrays = new int[n];
  int dp[][] = new int[n][n];
  for (int i = 0; i < arrays.length; i++) {
    arrays[i] = scanner.nextInt();
  }
  //l 是子问题的珠子数
  for (int l = 2;l <= n ; l++) {
      for (int i = 0; i < n; i++) {
       int j = (i+l-1) % n;
       for (int k = i ; k < i + l - 1; k++) {
         dp[i][j] = Math.max(dp[i][j], dp[i][k%n] + dp[(k+1)%n][j] + p(i,(k+1)%n,(j+1)%n));
       }
     }
  }
  int max = 0;
  for (int i = 0; i < n; i++) {
    max = Math.max(dp[i][(i+n-1)%n], max);
  }
  System.out.println(max);
}
//计算组合成新的能量
public static int p(int i,int k,int j) {    
  return arrays[i]*arrays[k]*arrays[j];
}


 

0.0分

8 人评分

  评论区

太牛了
2021-12-08 10:44:16 | |
取余容易出错,不不不是我太菜了,断环为链干它。
2021-08-25 11:35:59 | |
好强
2021-03-24 19:27:01 | |
实在是看不懂你讲的什么
2021-03-08 17:04:52 | |
能告诉我  你是怎么想的吗  有没有联系方式
我有很多想请教的
2021-02-20 14:04:55 | |
写的很棒
2021-02-09 23:32:42 | |
  • «
  • 1
  • »