区间DP
题单介绍
# 区间DP：用小的区间求出大的区间
[P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)&[P1063 [NOIP2006 提高组] 能量项链](https://www.luogu.com.cn/problem/P1063)都是直接从中间分成两半计算
[P2858 [USACO06FEB]Treats for the Cows G/S](https://www.luogu.com.cn/problem/P2858) 从dp[i][i]表示取第n个数开始转移，第n-1个数即可求得
```cpp
j=i+len-1,k=n-len+1;
dp[i][j]=max(dp[i][j],dp[i+1][j]+a[i]*k);//第k个数取a[i]
dp[i][j]=max(dp[i][j],dp[i][j-1]+a[j]*k);//第k个数取a[j]
```
[P3205 [HNOI2010]合唱队](https://www.luogu.com.cn/problem/P3205) 考虑新加入来的人是从左边进来的还是从右边进来的，分情况考虑
```cpp
int j=i+len-1;
if(len==1) dp[i][j][0]=1;//初始化
if(a[i]<a[i+1]) dp[i][j][0]+=dp[i+1][j][0];//a[i]从左边进来
if(a[i]<a[j]) dp[i][j][0]+=dp[i+1][j][1];//a[i]从左边进来
if(a[j]>a[i]) dp[i][j][1]+=dp[i][j-1][0];//a[j]从右边进来
if(a[j]>a[j-1]) dp[i][j][1]+=dp[i][j-1][1];//a[j]从右边进来
```
[P4170 [CQOI2007]涂色](https://www.luogu.com.cn/problem/P4170) 分两种情况考虑：a[i]==a[j]和a[i]!=a[j]
```cpp
int j=i+l-1;
if(l==1) dp[i][j]=1;
else
if(a[i]==a[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);//a[i]==a[j]时，可直接从这两个状态扩展一位得到而不增加涂色次数
else for(ri k=i;k<j;++k) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);//a[i]!=a[j]时，从中间选择一处断开成两个区间
```
[P3146 [USACO16OPEN]248 G](https://www.luogu.com.cn/problem/P3146)dp[i
][j]指该区间能够得到的最大数，然后一样从中间断开。
```cpp
int j=i+l-1;
if(l==1) dp[i][j]=a[i];
else
for(ri k=i;k<j;++k)
if(dp[i][k]==dp[k+1][j])//左右两边相等才能合并
dp[i][j]=max(dp[i][j],dp[i][k]+1);//求个最大的
ans=max(ans,dp[i][j]);
```
[P3147 [USACO16OPEN]262144 P](https://www.luogu.com.cn/problem/P3147)**貌似不是道区间DP题。**
神奇的状态：dp[i][j]表示以j为左端点能合成出i的右端点，然后状态转移方程就很显然了。
```cpp
int n=read(),ans=0;
for(ri i=1;i<=n;++i) dp[read()][i]=i+1;
for(ri i=2;i<=58;++i)
for(ri j=1;j<=n;++j)
{
if(!dp[i][j]) dp[i][j]=dp[i-1][dp[i-1][j]];//更新
if(dp[i][j]) ans=i;//答案是单调的
}
printf("%d",ans);
```
[P1220 关路灯](https://www.luogu.com.cn/problem/P1220)dp[i][j][0]指关掉区间i~j后停在i处的最小耗电量，dp[i][j][1]指停在j处的。状态转移方程有点长（a[i]是距离，s[i]是功率前缀和）
```cpp
int j=i+l-1;
dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1]-a[i])*(s[i]+s[n]-s[j]),dp[i+1][j][1]+(a[j]-a[i])*(s[i]+s[n]-s[j]));
dp[i][j][1]=min(dp[i][j-1][0]+(a[j]-a[i])*(s[i-1]+s[n]-s[j-1]),dp[i][j-1][1]+(a[j]-a[j-1])*(s[i-1]+s[n]-s[j-1]));
```