区间DP

区间DP做题记录。
【前言：这几天疯狂刷了会区间$DP$，总结一下。】
##一、总而言之
比较常见的设$f[x][y]$为在$x,y$这一段区间中最终可以合并成的（字符串）最小数值/得到的最大分数等等
转移状态中通常由以下模板（部分题目还是需要改动的）：

for(register int l=2;l<=n;++l)
    for(register int i=1;i+l-1<=n;++i){
        ll j=i+l-1;
        for(register int k=i;k<j;++k)
            f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
    
    }

##二、典型例题

1）$P1880 [NOI1995]$ 石子合并

标准模板题！可以在其中学到标准模板以及断环为链解法。

2）$P1220$ 关路灯&$P2466 [SDOI2008]Sue$的小球

另一类区间问题，核心思路是：

• 设$f[x][y][0/1]$表示已经处理完了$x-y$之间的路径，此刻正站在$x(f[x][y][0])$或者$y(f[x][y][1])$点
• 分别递推是如何得到现在这一步的？比如说$f[x][y][0]$就可以由$f[x-1][y][0]$等状态得到（在下面会列出完整版）
• $f[i][j][0]$可由$f[i + 1][j][0]$或$f[i + 1][j][1]$得到
• $f[i][j][1]$可由$f[i][j - 1][0]$或$f[i][j - 1][1]$得到
  在此时就不得不提一下我们的第三题了：

3）$P6879 [JOI 2020 Final] スタンプラリー 3$

这题感觉和关路灯很像阿可惜暂时看不懂题解（或许脑袋清醒一点的时候会看懂的吧！

4）$P4342 [IOI1998]Polygon$

阿，是玻璃筒呢！据说也是一款音游？
好题目。

• $f[x][y]$为合并$x$到$y$中间的最大值，$g[x][y]$为合并$x$到$y$中间的最小值
• 加法时
  $f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);$
  $g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);$
• 乘法时
  $f[i][j]=max(f[i][j],max(f[i][k]*f[k+1][j],g[i][k]*g[k+1][j]));$
  $g[i][j]=min(g[i][j],min(f[i][k]*f[k+1][j],min(f[i][k]*g[k+1][j],min(g[i][k]*f[k+1][j],g[i][k]*g[k+1][j]))));$
• 具体证明过程请看题解！（其实是笔者太懒了
  ####5）$P4302 [SCOI2003]$字符串折叠&$P2470 [SCOI2007]$压缩
  与字符串有关的区间$DP$。

#include <bits/stdc++.h>
#define ll long long
#define maxn 110
using namespace std;
string nw;
ll n,k[maxn],f[maxn][maxn];

inline int check(ll l,ll r,ll ln){
	for(register int i=l;i<=r;++i)
		if(nw[i]!=nw[(i-l)%ln+l])//判断重复：区间i到j中是否存在长度为ln的循环
			return false;
	return true;
}

int main(){
	cin>>nw;
	n=nw.size();
	nw=' '+nw;//让nw中的每个字符下标加一
	for(register int i=1;i<=9;++i)	k[i]=1;
	for(register int i=10;i<=99;++i)k[i]=2;
	k[100]=3;//算常数的位数
	memset(f,0x3f3f3f3f,sizeof f);
	for(register int i=1;i<=n;++i)
		f[i][i]=1;
	for(register int l=2;l<=n;++l)
		for(register int i=1;i+l-1<=n;++i){
			ll j=i+l-1;
			for(register int tk=i;tk<j;++tk)
				f[i][j]=min(f[i][j],f[i][tk]+f[tk+1][j]);//先试着把不能压缩的压缩完
			for(register int tk=i;tk<j;++tk){
				ll len=tk-i+1;//算循环节长度
				if(l%len)	continue;//如果都不整除那就算了吧
				if(check(i,j,len))
					f[i][j]=min(f[i][j],f[i][tk]+2+k[l/len]);//如果整除，循环部分+（）+常数的位数
			} 	
		
		}
	printf("%lld ",f[1][n]);
	return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define maxn 55
using namespace std;
string nw;
ll len,dp[maxn][maxn][3];
//dp[x][y][1/0]表示在x到y区间内是/否有m的最小长度
//nw是原字符串

inline int check(ll l,ll r){
    if((r-l+1)&1)   return 0;
    ll mid=(l+r)>>1;
    for(register int i=l;i<=mid;++i)
        if(nw[i]!=nw[i+mid-l+1])//i+mid-l-1自己手动模拟以下是可以判重复的
            return 0;
    return 1;
}

int main(){
    cin>>nw;
    len=nw.size();//获得字符长度
    memset(dp,0x3f,sizeof(dp));//清最大值
    for(register int i=1;i<=len;++i)
        for(register int j=i;j<=len;++j)
            dp[i][j][0]=dp[i][j][1]=(j-i+1);//初始值都是段落长度（m留给下面处理了这里并不需要将dp[i][j][1]加上1
    for(register int l=2;l<=len;++l)
        for(register int i=1;i+l-1<=len;++i){
            ll j=i+l-1;
            if(check(i-1,j-1))
                dp[i][j][0]=min(dp[i][(i+j)>>1][0]+1,dp[i][j][0]);//如果有重叠的那么加上R（这里在前面那一段使用的是不含m的段，如果有m的话那么就会导致重复部分混乱），至于m会在下面处理这里并不需要管
            for(register int k=i;k<j;++k)
                dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+(j-k));//如果没有m：直接在后面拼上一截，如果后面那一段有折叠的话，会在下面那个循环(dp[i][j][1])中处理
            for(register int k=i;k<j;++k)
                dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][0],dp[i][k][1])+min(dp[k+1][j][0],dp[k+1][j][1])+1);
                //k枚举的为m的位置，在前半段和后半段中分别取出一个最小的再在中间加上m（至于具体的R的位置并不需要管因为后面那一段如果有重复的话那么dp[k+1][j][1]肯定是小于dp[k+1][j][0]的）；如果后面那一段不可以折叠的话那么dp[i][j][0]肯定是小于dp[i][j][1]的（毕竟dp[i][j][1]要多一个1）
        }
    printf("%lld\n",min(dp[1][len][1],dp[1][len][0]));//最后输出最优的解
    return 0;
}
//最优划分只有一种，最小划分也一定是最优划分并且满足局部段落最小划分

6）$P6701 [POI1997] Genotype$

区间$DP$+状压$DP$，有多种情况可以得到同一个结果并且既要记录状态过程又要记录状态结果时需要用到状压
依旧是枚举断点将一个区间分为两个区间处理

7）$P4766 [CERC2014]Outer\ space\ invaders$

这里采用$set$和$lower\_bound$函数进行离散化并先处理好了区间最大值
区间最大值的处理方式首先是一个个扫处理$w[i].l$至$w[i].r$之间的最大值
然后再进行$DP$
$f[i][j]$可以由$f[i][j-1]$或$f[i+1][j]$得到

8）$P5851\ [USACO19DEC]Greedy\ Pie\ Eaters\ P$