能量项链oj23800

题目大意：

N（ 4 ≤ N ≤ 100 ），表示项链上珠子的个数

第二行是N个用空格隔开的正整数，所有的数均不超过1000。

第 i 个数为第 i 颗珠子的头标记（ 1 ≤ i ≤ N ），

当 1 ≤ i < N 时，第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。

第N颗珠子的尾标记应该等于第1颗珠子的头标记。

输出是一个正整数E（ E ≤ 2.1×10⁹ ），为一个最优聚合顺序所释放的总能量。

Sample Input

42 3 5 10

Sample Output

710

 

一道环形的矩阵连乘

#include <bits/stdc++.h> #define ll long long using namespace std; int main() { ll n,dp[105][105],a[105]; scanf("%lld",&n); for(int i=0;i<n;i++) scanf("%lld",&a[i]); for(int i=0;i<n;i++) fill(dp[i],dp[i]+105,0); for(int i=0;i<n;i++) /// 先处理初始状态 最少为相邻两个聚合 即长度为2 dp[i][(i+1)%n]=a[i]*a[(i+1)%n]*a[(i+2)%n]; /// 环形 注意各个位置的求模 i为0~n-1 模n恰好 ll ans=0; for(int i=3;i<=n;i++) // 枚举长度 从3开始 for(int l=0;l<n;l++) { // 枚举开头 int r=(l+i-1)%n; // 得到该长度时的最右端 for(int k=1;k<i;k++) { // 枚举分段的长度 int m=(l+k-1)%n; // 得到该分段的最右端 dp[l][r]=max(dp[l][r], dp[l][m]+dp[(m+1)%n][r]+a[l]*a[(m+1)%n]*a[(r+1)%n]); } /// 左端+右端+左右两端聚合所得能量 if(i==n) ans=max(ans,dp[l][r]); // 更新答案 } printf("%lld",ans); return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/9148735.html

相关资源：JAVA上百实例源码以及开源项目