区间DP

[post cid=”15” /]
区间DP类似于记忆化搜索，只是将树形的结构使用循环完成，时间复杂度一般为$O(n^3)$

代码实现

for (int len=2;len<=n;++len){  //枚举区间的长度，因为大的区间状态需要有小的状态转移过来，因此从小到大枚举
    for (int i=1;i+len-1<=n;++i){  //枚举起点
        int j=i+len-1;  //计算终点
        for (int k=i;k<=j-1;++k) ... // 转移
    }
}

例题

石子合并P281
DP数组储存这一区间中合并的最小值，状态转移方程为
$$F_{i,j}=min(F_{i,k}+F_{k+1,j})+\sum_{k=i}^{j}a_{k}$$
注意这里不能直接在DP数组上进行操作，必须额外加上i-j的和才行

#include <bits/stdc++.h>
using namespace std;

int n,a[305],f[305][305],sum[305];
int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    memset(f,0x3f,sizeof f);
    for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i],f[i][i]=0;
    for (int len=2;len<=n;++len){
        for (int i=1;i+len-1<=n;++i){
            int j=i+len-1;
            for (int k=i;k<=j-1;++k){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
            f[i][j]+=sum[j]-sum[i-1];
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

多边形游戏P282
将环形展开处理，枚举断开的边即可，注意可能有负负得正的情况，因此需要记录一个最大值和最小值，然后在乘法处理的时候特殊判断即可

#include <bits/stdc++.h>
using namespace std;

int f[105][105],g[105][105],ans=-1e9,ansid,n;

struct node{
    int v;
    char op[4];
}a[105];

int main(){
    cin>>n;
    for (int i=1;i<=n;++i){
        scanf("%s %d",a[i].op,&a[i].v);
        a[i+n]=a[i];
    }
    memset(f,0x80,sizeof(f));
    memset(g,0x3f,sizeof(g));
    for (int i=1;i<=2*n;++i){
        f[i][i]=a[i].v;
        g[i][i]=a[i].v;
    }
    for (int st=1;st<=n;++st){
        for (int len=2;len<=n;++len){
            for (int i=1;i+len-1<=n;++i){
                int j=i+len-1;
                int l=i+st-1,r=j+st-1;
                for (int k=l;k<r;++k){
                    if(a[k+1].op[0]=='x'){
                        f[l][r]=max(f[l][r],max(f[l][k]*f[k+1][r],max(g[l][k]*g[k+1][r],max(f[l][k]*g[k+1][r],g[l][k]*f[k+1][r]))));
                        g[l][r]=min(g[l][r],min(f[l][k]*f[k+1][r],min(g[l][k]*g[k+1][r],min(f[l][k]*g[k+1][r],g[l][k]*f[k+1][r]))));
                    }
                    else if(a[k+1].op[0]=='t'){
                        f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
                        g[l][r]=min(g[l][r],g[l][k]+g[k+1][r]);
                    }
                }
            }
        }
        ans=max(ans,f[st][st+n-1]);
    }
    cout<<ans<<endl;
    for (int i=1;i<=n;++i) if(f[i][i+n-1]==ans) cout<<i<<' ';
    return 0;
}

金字塔P284
因为有房间一进一出，所以一旦存在$S_i=S_j$则i-j可能为其中的一个子树的遍历，不断累加答案即可
但是一个区间可能存在多颗子树，所以枚举中间的断点为第一颗子树的结束位置，在乘上后面的可能方案累加到该区间的答案中即可
状态转移如下：

对于区间S[i,j]

1. 根节点i
2. 第一颗子树[i+1,k-1]
3. 剩余的子树[k,j]
   因为每颗子树遍历完后都会回到根节点，因此Si==Sk==Sj

$$F_{i,j}=F_{i+1,k-1}*F_{k,j} (S_i=S_j=S_k,S_{i+1}=S_{k-1})$$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char s[305];
ll f[305][305],n,mod=1e9;

int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for (int len=1;len<=n;++len){
        for (int i=1;i+len-1<=n;++i){
            int j=i+len-1;
            if (len==1){
                f[i][j]=1;
            }else{
                for (int k=i+2;k<=j;++k){
                    if (s[i+1]==s[k-1] && s[k]==s[j]){
                        f[i][j]+=f[i+1][k-1]*f[k][j]%mod;
                        f[i][j]%=mod;
                    }
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/92/