dp问题

1.区间dp

P1063 [NOIP2006 提高组] 能量项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对于环形问题，我们常常可以采用将n个元素复制成2n个元素，或者选择(i + 1) % n的形式

第一次遇到区间dp，写个题解总结一下

区间dp能解决的问题就是通过小区间更新大区间，最后得出指定区间的最优解。

想要用区间dp解决问题，首先要确定一个大问题能够剖分成几个相同较小问题，且小问题很容易组合成大问题，从而从解决小问题逐渐解决大问题，体现的其实是分治的思想，只不过是通过dp用递推的方式解决了。

本题应通过演算过程发现最终问题的解决可由两个相同规模较小的问题轻松地转化过来。（一般分治时只分成两个简化程序） 用f[l][r]表示以a[l]开头a[r]结尾的数串的最大和，如k为i,j之间任一节点，有f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); 对l,r的定义自己一定要十分清晰，从而确定好循环的边界。

但也有问题随之而来，在更新时要将2*n个元素都更新，而不能只更新到前n个，否则访问到n+1~2n时会出错

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 410;
 5 int f[N][N];
 6 int n,a[205]; 
 7 int main()
 8 {
 9     cin >> n;
10     for(int i=1;i<=n;i++)  //***对环形问题的处理技巧***
11     {
12         cin >> a[i];
13         a[n+i]=a[i];
14     } 
15     
16     //可以视为项链每3个为一个区间
17     for(int i = 2;i <= n + 1;i ++)
18     {
19         //更新区间起点
20         for(int l = 1;l + i - 1 <=2 * n;l ++)  //如果采取了上述策略，一定要将2*n个点都更新 
21         {
22             int r = l + i - 1; //区间末端
23             for(int k = l + 1 ;k <= l + i - 2;k ++)//区间中的断点，表示项链的第三个点
24                 f[l][r]=max(f[l][r],f[l][k]+f[k][r] + a[l] * a[k] * a[r]); 
25         }
26     }
27     
28     int res = 0;
29     for (int i = 1;i <= n;i ++) res = max(res,f[i][n + i]);
30     cout << res;
31     return 0;
32 }