入门区间dp
默认读者已经对区间dp有所了解
一、定义
区间dp顾名思义是在区间上DP，它的主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。
二、基础模板（石子合并）
for(int len=2;len<=n;len++) //区间长度
{
for(int i=1;i<=n;i++) //左端点，后面会用l替换
{
int j=i+len-1; //右端点，后面会用r替换
if(j>n) continue; //右越界
for(int k=i;k<j;k++) //枚举中点
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
三、例题
状态转移方程 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
注意加上前缀和来记录区间[i,j]内的石子总重。
本题数据较小，不需要用到优化，可以直接进行区间dp，是一道入门的好题
#include<bits/stdc++.h>
using namespace std;
const int N=305;
int sum[N];
int dp[N][N];
int n,x;
int main()
{
cin>>n;
memset(dp,0x3f3f3f3f,sizeof(dp));
sum[0]=0;
for(int i=1;i<=n;i++)
{
cin>>x;
sum[i]=sum[i-1]+x;
dp[i][i]=0;
}
for(int len=2;len<=n;len++)
{
for(int i=1;i<=n;i++)
{
int j=i+len-1;
if(j>n) continue;
for(int k=i;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
cout<<dp[1][n];
}
2、石子合并（进阶版）
需要进行优化，感觉跟区间dp关系不大，本文最后贴代码
3、石子合并（环模型）
个人认为做区间dp的题目，环模型是一个十分经典的模型，可以区间的首尾进行相应操作
而将环展开成链是一个很好的解题方法
本题还需要注意的是要求最大值和最小值两个值，所以需要定义两个数组分别来进行区间dp，同时因为我们将环打开成链，最后还需遍历区间长度为n的两数组来找出最值
状态转移方程
最大值：dp1[i][j]=max(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);
最小值：dp2[i][j]=min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
遍历
int maxn=0,minn=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
maxn=max(maxn,dp1[i][i+n-1]);
minn=min(minn,dp2[i][i+n-1]);
}
下面是完整代码
#include<bits/stdc++.h>
using namespace std;
int n,x;
int a[205];
int sum[205];
int dp1[205][205];
int dp2[205][205];
int main()
{
cin>>n;
sum[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++)
{
sum[i]=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=2*n;i++)
{
int j=i+len-1;
dp1[i][j]=0;
dp2[i][j]=0x3f3f3f3f;
for(int k=i;k<j;k++)
{
dp1[i][j]=max(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);
dp2[i][j]=min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
}
}
}
int maxn=0,minn=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
maxn=max(maxn,dp1[i][i+n-1]);
minn=min(minn,dp2[i][i+n-1]);
}
cout<<minn<<endl<<maxn;
}
说三个石子合并了，下面说两题其他故事背景的模板题
4、能量项链
这题也是一个环模型，个人认为捋清楚关系之后会发现本题跟上面环模型的石子合并除开转移方程外基本一样。
重点不是本题，就不画图了，直接上代码
状态转移方程 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=210;
int n;
ll a[N];
ll sum[N];
ll dp[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
for(int len=3;len<=n+1;len++){
for(int i=1;i<=2*n;i++){
int j=i+len-1;
if(j>2*n) continue;
for(int k=i+1;k<j;k++){
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
}
}
}
ll maxn=-inf;
for(int i=1;i<=n;i++){
maxn=max(maxn,dp[i][i+n]);
}
cout<<maxn;
}
5、关路灯这题是弱弱做的一题道区间dp蓝题，还是学到不少东西
题意：老张需要关掉一条路上所有路灯，每秒可以移动1米，每秒亮着的灯会消耗一定的能量，问老张怎样的关灯的顺序可以使灯的总耗能最小。老张初始位置在某一灯位置，位置由输入给出
做题过程：开始当之前的二维dp做了，大意了啊，发现当成二维区间dp会出现某些没有考虑的情况，如最后老张的位置。所以本题需要采用三维区间dp。
本蒟蒻觉得二维还是有可写性的，深造一番再来写一发，现在就不口糊了
进入正题（思路）：每一次老张走都可以选向左或者向右走去关最优的那一盏灯，也是离当前位置最近的左右两张灯中最优的那一盏。（理由就是没有理由，这是小学常识 ）
当然我们也不需要考虑上面说的这一点，我们只需要知道老张到达某一位置是从左边还是右边走来即可，通过多开一维数组来记录，剩下的就是一些细节问题。
状态转移方程
if(l>1){
dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][0]+(a[l].x-a[l-1].x)*cal(l,r));
dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][1]+(a[r].x-a[l-1].x)*cal(l,r));
}
if(r<n){
dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][0]+(a[r+1].x-a[l].x)*cal(l,r));
dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][1]+(a[r+1].x-a[r].x)*cal(l,r));
}
因为每盏灯只有位置和功率两种信息，所以这里采用pair来记录信息。
下面给出全部代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PLL;
int n,c;
int dp[60][60][2];
PLL a[60];
int cal(int l,int r){
int ans1=0,ans2=0;
for(int i=1;i<=n;i++) ans1+=a[i].y;
for(int i=l;i<=r;i++) ans2+=a[i].y;
return ans1-ans2;
}
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
memset(dp,0x3f3f,sizeof(dp));
dp[c][c][0]=0,dp[c][c][1]=0;
for(int len=0;len<n;len++){
for(int l=1;l<=n-len;l++){
int r=l+len;
if(l>1){
dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][0]+(a[l].x-a[l-1].x)*cal(l,r));
dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][1]+(a[r].x-a[l-1].x)*cal(l,r));
}
if(r<n){
dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][0]+(a[r+1].x-a[l].x)*cal(l,r));
dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][1]+(a[r+1].x-a[r].x)*cal(l,r));
}
}
}
cout<<min(dp[1][n][0],dp[1][n][1])<<endl;
}
总结：还是得多刷题，多思考
完结撒花
后记：石子合并优化（GarsiaWachs算法）
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N = 50005;
const int INF = 0x3f3f3f3f;
int stone[N];
int n,t,ans;
void combine(int k)
{
int tmp = stone[k] + stone[k-1];
ans += tmp;
t--;
for(int i=k;i<t;i++)
stone[i] = stone[i+1];
int j = 0;
for(j=k-1;stone[j-1] < tmp;j--)
stone[j] = stone[j-1];
stone[j] = tmp;
while(j >= 2 && stone[j] >= stone[j-2])
{
int d = t - j;
combine(j-1);
j = t - d;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&stone[i]);
stone[0]=INF;
stone[n+1]=INF-1;
t = 3;
ans = 0;
for(int i=3;i<=n+1;i++)
{
stone[t++] = stone[i];
while(stone[t-3] <= stone[t-1])
combine(t-2);
}
while(t > 3) combine(t-1);
printf("%d\n",ans);
memset(stone,0,sizeof(stone));
return 0;
}
石子合并优化建议看这个大佬的博客园：
石子合并优化分析