整理区间DP例题以及对区间DP理解
区间DP，即合并类动态规划，往往以区间为阶段进行划分
在解决区间合并问题时：
1.以区间长度为阶段
2.以左右端点为状态
3.以区间划分为决策
另一种写法以左端点为阶段，右端点为状态直接枚举决策
这种写法是可行的
还有是要注意写法：
伪代码模板
void DP(){
for(阶段){
for(状态){
for(决策){
状态转移方程；
}
}
}
for(阶段){
答案=最优决策;
}
}
例题：
石子合并：
1.线性：
这里就直接套上述区间dp设计模板即可：
1.以区间长度为阶段：区间长度从2到n；
2.以左右端点为状态：枚举左端点求右端点即可确定状态；
3.以断点枚举为决策：从左端点枚举断点到右端点，推出状态转移方程
显然：如果以k为断点，那么最优状态无非就是在k断开时最优解与不在k断开时的最优解两者中更优的那一个
因此，我们得出状态转移方程：
f[i][j]=max(f[i][k]+f[k+1][j],f[i][j]),(i<=k
code
线性
#include
using namespace std;
int n,maxn=-2147483647,minn=2147483647;
const int p=1010;
int u[p][p],d[p][p],f[p],sum[p];
void in(){
memset(d,0x7f,sizeof(d));
memset(u,0xcf,sizeof(u));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&f[i]);
sum[i]=sum[i-1]+f[i];
u[i][i]=0;
d[i][i]=0;
}
}
void work(){
for(int len=2;len<=n;len++){
for(int l=1;l<=n;l++){
int r=l+len-1;
for(int k=l;k
2.环形（NOI1995）
与线性不同的是环形，那么，环形的处理办法？
化环成链：即把环形的数据结构通过复制并连接在原数据结构后边，实现环中每一个合法的链（可能不是最大）在新数据结构中都存在一段连续的数列与之相对应的方法
这种拆环的手段在环形区间DP中是一种常用的处理手段
不过要注意一个小细节,就是拆环以后的最大合法长度是n，但是数据的长度是2n，因此左端点的枚举也要到2n-1-len的位置
剩下的部分我们已经将环拆成链了，因此与线性的是一样的了
code
环形
#include
using namespace std;
int n,maxn,minn=0x7f7f7f7f;
const int p=2e3;
int u[p][p],d[p][p],f[p],sum[p];
void in(){
memset(d,0x7f,sizeof(d));
memset(u,0xcf,sizeof(u));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&f[i]);
f[i+n]=f[i];
}
}
void change(){
for(int i=1;i<=2*n;i++){
sum[i]=sum[i-1]+f[i];
u[i][i]=0;
d[i][i]=0;
}
}
void work(){
for(int len=2;len<=n;len++){
for(int i=1;i<=2*n-len;i++){
int j=i+len-1;
for(int k=i;k
3.优化
1.四边形不等式优化DP：
四边形不等式：由于不好整图片就直接上OIwiki的链接了
该优化可以将原本O(n3)的时间复杂度优化到O(n2)
但是由于空间复杂度也是O(n2)，因此最大数据规模约为n=5700，再向上增加n就可能会爆空间
四边形不等式优化DP
#include
using namespace std;
int n,maxn;
const int p=5e3;
int u[p][p],f[p],sum[p];
void in(){
memset(u,0xcf,sizeof(u));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&f[i]);
f[i+n]=f[i];
}
}
void change(){
for(int i=1;i<=2*n;i++){
sum[i]=sum[i-1]+f[i];
u[i][i]=0;
}
}
void work(){
for(int d=2;d<=n;d++){
for(int i=1,j;(j=i+d-1)<=2*n;i++){
u[i][j]=max(u[i][j-1],u[i+1][j])+sum[j]-sum[i-1];
}
}
for(int i=1;i<=n;i++){
maxn=max(maxn,u[i][i+n-1]);
}
}
void out(){
printf("%d\n",maxn);
}
int main(){
in();
change();
work();
out();
return 0;
}
2.专门算法（SDOI2008）
GarsiaWachs算法
我专门查了这个算法然而只查到写法没查到证明本蒟蒻fw一个不会证略了
这个算法是用来求线性石子合并类型中的最大值，可以把时间复杂度干到O(nlogn)
然而能解决的类型实在少，谁叫这玩意nlogn
贴code跑路
GarsiaWachs
#include
using namespace std;
#define maxn 50010
typedef long long ll;
ll st[maxn];
int n,t;
ll ans;
inline void combine(int x){
ll tmp = st[x] + st[x - 1];
ans += tmp;
for(int i = x;i < t - 1;i++){
st[i] = st[i + 1];
}
t--;
int j = 0;
for(j = x - 1;j > 0 && st[j - 1] < tmp;j--){
st[j] = st[j - 1];
}
st[j] = tmp;
while(j >= 2 && st[j] > st[j - 2]){
int d = t - j;
combine(j - 1);
j = t - d;
}
}
int main() {
//ios::sync_with_stdio(0); cin.tie(0);
int n;scanf("%d",&n);
for(int i = 0;i < n;i++)scanf("%lld",&st[i]);
t = 1;ans = 0;
for(int i = 1;i < n;i++){
st[t++] = st[i];
while(t >= 3 && st[t - 3] <= st[t - 1]){
combine(t - 2);
}
}
while(t > 1)combine(t - 1);
printf("%lld\n",ans);
return 0;
}
能量项链/矩阵连乘/三角划分：
这类是相乘的并且首尾相接
但是还是区间合并类DP
因此还是三件套：
区间长——阶段，左右端点——状态，断点——决策
1.矩阵连乘（线性）
还是以断点列状态转移方程
断点左：左端点到断点的最优状态
断点右：断点右一到右端点的最优状态
处理断点：左端合并完毕剩下左端点头，断点的尾（即断点右一）
同理：右端合并完毕后剩下断点右一的头，右端点的尾
合并后的总运算量：断点计算量+断点左，右的最优计算量
与不断开相比，最优运算量应是两者较小值，因此：
状态转移方程：
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[i]Xa[k+1]Xa[j+1])
i为左端点，j为右端点，k为断点，i<=k
细节处理：要把f数组初始化为0x3f3f3f3f，以得出最小值
code
矩阵连乘
#include
using namespace std;
const int p=1e3;
int n,ans,f[p][p],a[p];
void in(){
memset(f,0x7f,sizeof(f));
scanf("%d",&n);
for(int i=1;i<=n+1;i++){
scanf("%d",&a[i]);
f[i][i]=0;
}
}
void work(){
for(int i=2;i<=n+1;i++){
for(int j=i-1;i-j
2.能量项链（环形）
环形版矩阵连乘求最大值而已。。。
不用赋初值但是要拆环
状态转移方程与上面同类，分析过程同理
所以我直接打状态转移方程跑路
状态转移方程：
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]Xa[k+1]Xa[j+1]);
code
点击查看代码
#include
#include
#include
#include
#include
#define INF -0xfffffff;
using namespace std;
const int N=1000;
int shu,maxx=0;
int f[N][N];
int a[N];
int main()
{
scanf("%d",&shu);
memset(f,0xcf,sizeof(f));
for(int i=1;i<=shu;i++) scanf("%d",&a[i]),a[shu+i]=a[i];
for(int i=1;i<=shu*2;i++) f[i][i]=0;
for(int d=2;d<=shu*2;d++)
{
for(int i=1,j=0;(j=d+i-1)<=shu*2;i++)
{
for(int k=i+1;k
三角剖分
这题也是个区间合并类，也是个环型，不过因为是连线，可看做“某种程度上顺序不同的方案可看做同种方案”，于是按环形考虑时，原本的“半实半虚”状态在跑1到n时跑过了可以不跑，因此当成线性打也是正确的
状态转移方程：
f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]Xa[j]Xa[k]);
code
点击查看代码
#include
using namespace std;
const int p=222;
long long n,a[p],f[p][p],ans;
void in(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
a[i+n]=a[i];
}
}
void change(){
memset(f,0x3f,sizeof(f));
for(int i=1;i<=2*n;i++){
f[i][i]=0;
f[i][i+1]=0;
f[i][i-1]=0;
}
}
void work(){
for(int i=1;i<=n;i++){
for(int j=i+2;j<=i+n-1;j++){
for(int k=i+1;k
乘积最大/整数划分
添乘号，添和不添进行状态转移
直接上code
点击查看代码
#include
using namespace std;
const int p=1e3+10;
#define llg long long
int a[p],n,T,pa[p][p],m;
llg dp[p][p],sum[p][p];
char s[p];
void change(){
n=strlen(s+1);
memset(sum,0,sizeof(sum));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
sum[i][j]=sum[i][j-1]*10+s[j]-'0';
}
}
for(int i=1;i<=n;i++){
dp[i][0]=sum[1][i];
}
}
void path(int x,int t){
if(t==-1){
return ;
}
path(pa[x][t],t-1);
printf("%lld ",sum[pa[x][t]+1][x]);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%s%d",s+1,&m);
m--;
change();
for(int i=1;i<=n;i++){
for(int j=1;j<=min(i-1,m);j++){
for(int k=1;k
Polygon
由于“负负得正”的性质，我们不仅要维护最大值，也要维护最小值
加法：满足贪心性质，不用特殊处理
乘法：最大：“最小乘最小”和“最大乘最大”同时维护，取最优解
最小：“最小乘最小”，“最大乘最小”两种
再加上区间DP即可
Code
Polygon
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=125;
int f[MAXN][MAXN],f1[MAXN][MAXN],a[MAXN],n;
char b[MAXN];
int main()
{
scanf("%d",&n);
memset(f,-0x3f,sizeof(f));
memset(f1,0x3f,sizeof(f1));
for(int i=1;i<=n;i++){
getchar();
scanf("%c%d",&b[i],&a[i]);
b[i+n]=b[i];a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++){
f1[i][i]=f[i][i]=a[i];
}
for(int i=2;i<=n;i++){
for(int l=1;l<=n*2-i+1;l++){
int r=l+i-1;
for(int k=l;k
航线：SBLIS