区间dp 能量项链洛谷p1063

题目大意：如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为

（Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

这个题就是很裸的一个区间dp题虽然他巴拉巴拉说了一堆）：
首先我们枚举一下区间首先枚举长度然后枚举一下左端点右端点

这里的能量项链既然是项链就是个环那处理环的区间问题的时候就把长度开为二倍，然后存的时候 i+n 存和 i 一样的东西就好了

这里注意一下枚举左端点的时候范围应该是<=2*n - len，不然会越界

然后开始dp就好了

看题）：让我们直接跳过巴拉巴拉巴拉的地方找出我们的dp方程

所以我们的dp方程咧那就是

解释一下就是从l到r能取得的最大值就是l 到 i 的最大值加i 到 r的最大值加 i这个点连接之后爆发的能量

上代码

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = 1e3+;

 int n,a[maxn],dp[maxn][maxn],ans;

 int main(){

     scanf("%d",&n);

     for(int i = ;i <= n;++i){

         scanf("%d",&a[i]);

         a[i+n] = a[i];

     }

     for(int len = ;len <= n;++len){

         for(int l = ;l <= *n - len;++l){

             int r = l + len;

             for(int i = l + ;i <  r;++i)

                 dp[l][r] = max(dp[l][r],dp[l][i] + dp[i][r] + a[l]*a[i]*a[r]);

         }

     }

     for(int i = ;i <= n;++i)ans = max(ans,dp[i][i+n]);

     printf("%d",ans);

     return ;

 }

感谢观看

>_<

巴特西

区间dp 能量项链洛谷p1063

最新文章

热门文章

巴特西

区间dp 能量项链 洛谷p1063

最新文章

热门文章

区间dp 能量项链洛谷p1063