区间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));
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！