题解 P1063 【能量项链】
Valhalla_Is_Calling
2019-07-20 19:37:38
## 最近学习了区间DP，来写题解
### DP主要的核心就是对于每道题专属的状态转移方程
#### 动态规划过程是：
每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划(DP)。
#### 基本思想与策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
#### 动态规划的算法设计
1：找出最优解的性质，并描述其结构特征
2：递归定义最优值
3：以自底向上的方式计算最优值
4：根据计算最优值时得到的信息构造出最优解
能采用动态规划求解的问题的一般要具有3个性质
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
使用动态规划求解问题，最重要的就是确定动态规划三要素
（1）问题的阶段
（2）每个阶段的状态
（3）从前一个阶段转化到后一个阶段之间的递推关系。
#### 动态规划的具体步骤：
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
本题思路：与其他区间DP的题目不同，能量石排列成了一个环形，所以：
```cpp
for(i=1;i<=n;i++)
{
cin>>head[i];
head[i+n]=head[i];
}
for(i=1;i<=2*n-1;i++) tail[i]=head[i+1];
tail[2*n]=head[1];
```
必须使用这段复杂但有趣的环形初始化过程
之后，就要对F数组进行动态规划，选择出最值的合并方法
```cpp
for(t=1;t<=n-1;t++)
{
for(i=1;i<=2*n-t;i++)
{
j=i+t;
for(k=i;k<=j-1;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
}
}
}
```
状态转移方程是：
```cpp
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
```
原因是：K循环和I循环寻找的是石头的头和尾，所以要
和后面的方程式进行判断，更新最大值。
下面粘完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int head[205],tail[205],f[205][205]={0};
int main()
{
int ans=0,n,i,t,j,k;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>head[i];
head[i+n]=head[i];
}
for(i=1;i<=2*n-1;i++) tail[i]=head[i+1];
tail[2*n]=head[1];
for(i=1;i<=2*n-1;i++) f[i][i]=0;
for(t=1;t<=n-1;t++)
{
for(i=1;i<=2*n-t;i++)
{
j=i+t;
for(k=i;k<=j-1;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
}
}
}
for(i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);
cout<<ans<<endl;
return 0;
}
```
## 杜绝抄袭，请勿作弊