区间dp模板
区间dp模板
区间dp可以分为几类分支。环形区间dp,区间dp记录方案数,区间dp和高精度结合,二维区间dp
环形区间dp
将环拆开,采用复制的方法,延长长度至2倍
1068. 环形石子合并
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
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;
}
#include <iostream>
#include <cstring>
#include <cstdio>
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记录方案数
#include<iostream>
#include<cstdio>
#include<cstring>
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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
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(" d",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<<w[i]<<" "<<w[j]<<" "<<" "<<w[k]<<endl;
// print(ans);
// cout<<k<<" ";
// 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 <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
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));
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbhci
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01