@suixinhita 2017-10-10T08:29:45.000000Z 字数 4005 阅读 1294

区间DP

区间DP是个好东西（。）水了几道题。
一般说来，区间DP是一个很容易想到的地方，方程也非常好设置，一般是这样的：

$dp[i][j][k](k=0/1)$
其中，

$i$ ,

$j$ 分别表示左右端点，

$k$ 一般用来表示另外一个状态量（有

$k$ 存在时，多选用递归求解。）
对于一般的没有

$k$ 的区间DP来说，我们选择递推解决，会比较方便。

递推~~套路（？？？）~~如下：

    for(int l=2;l<=n;++l)
        for(int i=1;i+l<=n;++i)
        {
            int j=i+l;
            for(int k=i;k<=j;++k)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j]);
        }

需要注意的几个点

1.区间长度从 $2$ 开始， $1$ 是留给初始化的。
2. $k$ 是严格小于 $j$ 的。
3.个别题目可以使用平行四边形优化。

所以还是扯一下平行四边形优化。
准确的说，平行四边形优化就是在转移的时候，把转移的状态记录下来了。
也就是，记忆化了每一个 $k$
这样的话，我们在枚举 $k$ 的时候就会有了一个很小的区间。
通常来说是

$mark[i][j-1]<=k<=mark[i][j+1]$

这样可以优化掉一层复杂度。
但是不幸的是，不是每一个区DP都可以这样优化的。
数学分析对于这个优化是比较难的，所以我们可以直接打表寻找是否可以使用。
打表之后，如果每一行或者每一列都是单调的，就可以放心平行四边形优化了。

比如这样：

    for(int l=2;l<=n;++l)
    {
        for(int i=1;i+l-1<=n;++i)
        {
            int j=i+l-1;
            dp[i][j]=inf;
            for(int k=s[i][j-1];k<=s[i+1][j];++k)//首先说一下这里是i j-1到
                //i+1 j 后面这个注意
            {
                if(dp[i][j]>dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1])
                    //k+1 i-1注意
                {
                    dp[i][j]=dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1];
                    s[i][j]=k;
                }
            }
        }
    }

就是这样的了~

再说一下对于状态的转移（一般说来情况并不多）：

1.对于大部分裸一点的DP问题，可以很明确的知道合并区间所需代价。
2.对于区间合并后会出现两个区间合并的代价未知的情况，比如括号的合并，就需要把很多状态抽象成一种，大多数时候是一定一动的抽象~~（这个比较...）~~稍后再分析。
3.对于状态转移多到要 狗带 的那些个状态，我们选择记忆化搜索。

那么现在就来说对于区间合并后的代价要判断的题目。

poj2955 括号匹配

题目意思很简单，就是给你一堆括号，问你这一堆里面，有多少个是匹配了的。

这个就需要我们抽象一下，因为在区间里面的没匹配的括号对于区间合并是非常不友好的，所以我们希望把这些去掉。
那么我们思考，对于两个区间里面的括号的匹配，其实我们都可以看做是另外两个每一个都自己匹配好了的区间 ~~这么绕口？？~~ 比如这样：

[ [ ( ( ] 和 ) ) ] == [ [ ( ( ] ) ) 和 ]

由此可以知道，对于区间合并，我们都可以抽象成两个区间两端的合并，因为剩下的在里面的会在枚举区间断点的时候枚举到，所以不会有状态没有枚举的情况。

/*
 括号匹配。
 把所有区间合并分为两个子问题。
 第一种是直接合并 eg.   (())  &&  {{}}[]
 第二种是包含性合并  eg.     (()  &&  {{[]}})
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=155;
const int inf=0x3f3f3f3f;
int dp[N][N];
char s[N];
bool check(char x,char y)
{
    if(x=='('&&y==')')  return 1;
    if(x=='['&&y==']')  return 1;
    return 0;
}
bool solve()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    if(s[1]=='e')   return 0;
    memset(dp,0,sizeof(dp));
    for(int l=2;l<=n;++l)
    {
        for(int i=1;i+l-1<=n;++i)
        {
            int j=i+l-1;
            if(check(s[i],s[j]))
                dp[i][j]=dp[i+1][j-1]+2;
            for(int k=i;k<j;++k)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
    }
    printf("%d\n",dp[1][n]);
    return 1;
}
int main()
{
    while(solve());
    return 0;
}

然后我们来说需要用到记忆化搜索的神题。
首先，这两道题非常相似，都是涉及了字符串的压缩。
所以对比一下

bzoj1068 & bzoj1090

1068

这道题的话，是把字符串的压缩，简化成了前后两半字符串的相等。因为这道题每次的压缩是不相等并且可以共有一个开头的。

1090

这道题是把字符串的压缩，变成了前后串判断是否可以压缩，也就是，后边的串是不是由前面的重复几遍得来的。

但是这两道题的DP方程是非常不一样的，1068的dp方程使用了前文提到的 $k$ 因为他可以共有开头 $M$ ，但1090不同，不需要 $k$ ，因为不能与前面一起用一个开头。

并且，对于为什么要选择对于1068判断的时候要用到剖成两半的方式，我想，还是因为这个题中，状态转移有很多种：

$k=1$ 时，
我们枚举区间中插 $M$ 的地方。那么前后我们就有四种可能性。

$k=0$ 时，
分为很多种情况，

后面可以压缩，因为我们假设每一个区间前面（ $l-1$ 处，都有一个 $M$ 。
2.后面不能压缩，所以我们直接加上后面的长度。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55;
const int inf=0x3f3f3f3f;
int dp[N][N][2],n;
char s[N];
bool check(int l,int r)
{
    if((r-l+1)&1)   return 0;
    int mid=l+r>>1;
    for(int i=l;i<=mid;++i)
        if(s[i]!=s[mid+i-l+1])  return 0;
    return 1;
}
int solve(int l,int r,int k)
{
    if(dp[l][r][k]<inf) return dp[l][r][k];
    int len=r-l+1;
    if(len==1)
    {
        if(k)   return dp[l][r][k]=inf;
        else    return dp[l][r][k]=1;
    }
    else
    {
        if(k)   
        {
            for(int i=l;i<r;++i)
            {
                dp[l][r][k]=min(dp[l][r][k],solve(l,i,1)+1+solve(i+1,r,1));
                dp[l][r][k]=min(dp[l][r][k],solve(l,i,1)+1+solve(i+1,r,0));
                dp[l][r][k]=min(dp[l][r][k],solve(l,i,0)+1+solve(i+1,r,1));
                dp[l][r][k]=min(dp[l][r][k],solve(l,i,0)+1+solve(i+1,r,0)); 
            }
            return dp[l][r][k];
        }
    }
    int mid=l+r>>1;
    if(check(l,r))  dp[l][r][k]=solve(l,mid,0)+1;
    for(int i=l;i<r;++i)
        dp[l][r][k]=min(dp[l][r][k],solve(l,i,0)+r-i);
    return dp[l][r][k];
}
int main()
{
    memset(dp,inf,sizeof(dp));
    scanf("%s",s+1);
    n=strlen(s+1);
    printf("%d\n",min(solve(1,n,0),solve(1,n,1)));
    return 0;
}

然后对于1090来说，我们就可以省略有没有 $M$ 的步骤，因为有没有这个，没关系的。
所以说我们直接暴力匹配前面和后面的串是不是循环，是了合并，不是直接加，简单粗暴（另外还有hash方式暴力匹配，不多说了。）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105;
const int inf=0x3f3f3f3f;
int dp[N][N],n;
char s[N];
int size(int len,int L)
{
    if(L/len<10)    return 1;
    if(L/len<100)   return 2;
    return 3;
}
bool check(int l,int r,int l2,int r2)
{
    int L=r-l+1,LL=r2-l2+1;
    if(L%LL!=0) return 0;
    for(int i=l;i<=r;++i)
    {
        int j=(i-l)%LL+l2;
        if(s[i]!=s[j])  return 0;
    }
    return  1;
}
int solve(int l,int r)
{
    if(l==r)    return 1;
    if(dp[l][r]!=inf)   return dp[l][r];
    int len=r-l+1;
    for(int i=l;i<r;++i)
    {
        len=min(len,solve(l,i)+solve(i+1,r));
        if(check(i+1,r,l,i))
            len=min(len,solve(l,i)+2+size((i-l+1),(r-l+1)));
    }
    return dp[l][r]=len;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(dp,inf,sizeof(dp));
    printf("%d",solve(1,n));
    return 0;
}