区间dp模板

区间dp模板

区间dp可以分为几类分支。

环形区间dp，区间dp记录方案数，区间dp和高精度结合，二维区间dp

环形区间dp

将环拆开，采用复制的方法，延长长度至2倍
1068. 环形石子合并

#include
#include
#include
#include
using namespace std;
const int maxn=405;
int dp1[maxn][maxn],dp2[maxn][maxn],w[maxn],n,s[maxn];

int main(void){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>w[i];
        w[i+n]=w[i];
    }
    for(int i=1;i<=2*n;++i) s[i]=s[i-1]+w[i];
    
    memset(dp1,-0x3f,sizeof dp1);
    memset(dp2,0x3f,sizeof dp2);
    for(int len=1;len<=n;++len){
        for(int i=1;i+len-1<=2*n;++i){
            int j=i+len-1;
            if(i==j){
                dp1[i][j]=dp2[i][j]=0;   
            }else{
                for(int mid=i;mid<j;++mid){
                    dp1[i][j]=max(dp1[i][j],dp1[i][mid]+dp1[mid+1][j]+s[j]-s[i-1]);
                    dp2[i][j]=min(dp2[i][j],dp2[i][mid]+dp2[mid+1][j]+s[j]-s[i-1]);
                }
            }
        }
    }
    int t1=-0x3f3f3f3f,t2=0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        t1=max(t1,dp1[i][i+n-1]);
        t2=min(t2,dp2[i][i+n-1]);
    }
    cout<<t2<<endl<<t1<<endl;
}

AcWing 320. 能量项链

#include 
#include 
#include 

using namespace std;

const int maxn = 210, inf=0x3f3f3f3f;
int w[maxn],dp[maxn][maxn],n;

int main(void){
     cin>>n;
     for(int i=1;i<=n;++i){
         cin>>w[i];
         w[i+n]=w[i];
     }
     for(int len=2;len<=n;++len){
         for(int i=1;i+len<=2*n;++i){
             int j=i+len;
             for(int mid=i+1;mid<i+len;++mid){
                 dp[i][j]=max(dp[i][j],dp[i][mid]+dp[mid][j]+w[i]*w[mid]*w[j]);
             }
         }
     }
     
     int ans=0;
     for(int i=1;i<=n;++i){
         ans=max(ans,dp[i][i+n]);
     }
     cout<<ans<<endl;
}

区间dp记录方案数

AcWing 479. 加分二叉树

#include
#include
#include
using namespace std;
const int maxn=40;
int n,w[maxn],dp[maxn][maxn],f[maxn][maxn];

void dfs(int l,int r){
    if(l>r) return;
    cout<<f[l][r]<<" ";
    dfs(l,f[l][r]-1);
    dfs(f[l][r]+1,r);
}

int main(void){
    cin>>n;
    for(int i=0;i<n;++i) cin>>w[i+1];
    
    memset(f,0x3f,sizeof f);
    for(int i=n;i>0;--i){
        for(int j=i;j<=n;++j){
            if(i==j) {
                dp[i][j]=w[i];
                dp[i][i-1]=1;
                f[i][i]=i;
            }else{
                for(int k=i;k<=j;++k){
                    int t=dp[i][k-1]*dp[k+1][j]+w[k];
                    if(t>dp[i][j] || (t==dp[i][j] && k<f[i][j])){
                        dp[i][j]=t;
                        f[i][j]=k;
                    }
                }
            }
        }
    }
    
    cout<<dp[1][n]<<endl;
    dfs(1,n);
}

区间dp和高精度结合

注意cmp的写法，如果两个vector有一个位置不相等，那么就能够判断大小

#include
#include
#include
#include
#include
using namespace std;

const int maxn=55,mod=1e9;
int n,w[maxn];
vector<int> dp[maxn][maxn];

void cmp(vector<int> &a,vector<int> b){
    int sa=a.size(),sb=b.size();
    if(sa==0 || sa>sb) {
        a=b;
    }else if(sa==sb){
        for(int i=sa-1;i>=0;--i){
            if(a[i]!=b[i]){
                if(a[i]>b[i]) a=b;
                break;
            }
        }
    }
}

vector<int> add(vector<int> &a,vector<int> &b,vector<int> &c){
    vector<int> tmp;
    long long t=0;
    int i=0;
    while(i<a.size() ||  i<b.size() || i<c.size() || t){
        if(i<a.size()) t+=a[i];
        if(i<b.size()) t+=b[i];
        if(i<c.size()) t+=c[i];
        tmp.push_back(t%mod);
        t/=mod;
        ++i;
    }
    return tmp;
}

void mul(vector<int> &a,int c){
    long long t=0;
    for(int i=0;i<a.size();++i){
        t=t+(long long)a[i]*c;
        a[i]=t%mod;
        t=t/mod;
    }
    if(t) a.push_back(t);
}

vector<int> mul(int a,int b,int c){
    vector<int> tmp;
    tmp.push_back(a);
    mul(tmp,b);
    mul(tmp,c);
    return tmp;
}

void print(vector<int> a){
    for(int i=a.size()-1;i>=0;--i){
        if(i!=a.size()-1)
            printf("%09d",a[i]);
        else printf("%d",a[i]);
    }
    cout<<endl;
}

int main(void){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>w[i];
    }
    // w[n+1]=w[1];
    for(int len=2;len<n;++len){
        for(int i=1;i+len<=n;++i){
            int j=i+len;
            for(int k=i+1;k<j;++k){
                vector<int> ans=mul(w[i],w[j],w[k]);
                // cout<
                // print(ans);
                // cout<
                // print(add(dp[i][k],dp[k][j],ans));
                cmp(dp[i][j],add(dp[i][k],dp[k][j],ans));
            }
        }
    }
    print(dp[1][n]);
}

二维区间dp

#include 
#include 
#include 
#include 

using namespace std;

const int maxn=16,n=8;
int m,w[maxn][maxn],s[maxn][maxn];
double X,dp[maxn][10][10][10][10];

double get(int x1,int x2,int y1,int y2){
    double delta=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
    delta=(delta-X)*(delta-X);
    return delta;
}


int main(void){
    cin>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>w[i][j];
        }
    }
    
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            s[i][j]=w[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    
    X=(double)s[n][n]/m;
    

    for(int k=1;k<=m;++k){
        for(int l=n;l>0;--l){
            for(int r=l;r<=n;++r){
                for(int d=n;d>0;--d){
                    for(int u=d;u<=n;++u){
                        
                        double &a=dp[k][l][r][d][u];
                        a=1e9;
                        
                        if(k==1){
                            a=get(l,r,d,u);
                            continue;
                        }
                        for(int t=l;t<r;++t){
                            a=min(a,dp[k-1][l][t][d][u]+get(t+1,r,d,u));
                            a=min(a,dp[k-1][t+1][r][d][u]+get(l,t,d,u));
                        }
                        for(int t=d;t<u;++t){
                            a=min(a,dp[k-1][l][r][d][t]+get(l,r,t+1,u));
                            a=min(a,dp[k-1][l][r][t+1][u]+get(l,r,d,t));
                        }
                    }
                }
            }
        }
    }
    printf("%.3lf\n", sqrt(dp[m][1][n][1][n]/m));
}