题解：P1063 [NOIP2006 提高组] 能量项链

这道题就是区间动态规划的一道超级~水~模版的一道题。与这道题几乎一模一样。

思路：

区间动态规划数组定义：就简单粗暴， $dp_{i,j}$ 表示区间 $[i，j)$ 中最大能量释放值。注意，区间是左闭右开。
确定区间分段。没有特殊限制，时间复杂度允许。循环 $k$ （区间 $[i,j)$ , $i<k<j$ ）。
状态转移方程。已知区间 $[i,j)$ ，断点 $k$ 。求 $dp[i][j]$ 。首先， $dp_{i,k}$ 与 $dp_{k,j}$ 合并。最后再加上断点左右的区间最大能量释放值就行了，即 $dp_{i,k}$ 与 $dp_{k,j}$ 的和。由题意，有以下计算代码：

CPP

int yh(int m,int r,int n){
	return m*r*n;
}//r,断点。m,区间[i,j)的i。n,区间[i.j)的j。

完整代码：

CPP

#include<bits/stdc++.h>
#define int long long
#include<iostream>
#define unsigned long long ull
using namespace std;
int yh(int m,int r,int n){
	return m*r*n;
}
const int N=210;
int a[N];
int dp[N][N];
int n;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];//环形，数组按照a[1]，……，a[n],a[1],……,a[n]存
	}
	n*=2;//环形，长度乘2。
	for(int len=2;len<=n;len++){//当前序列长度
		for(int i=1;i<=n-len+1;i++){//当前序列开头
			int j=i+len-1;//当前序列结尾
			for(int k=i+1;k<j;k++){//枚举断点
				dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+yh(a[i],a[k],a[j]));//状态转移
			}
		}
	}
	cout<<dp[1][n]/2;//n乘了2的，要除回去，或者循环在1~n,2~n+1,3~n+2……里面找最大值
	return 0;
}

题解：P1063 [NOIP2006 提高组] 能量项链

文章操作

相关推荐

评论

题解：P1063 [NOIP2006 提高组] 能量项链