企业官网建设流程全解析

区间DP就是dp数组维护区间范围内的要求值，大区间值与小区间有关，最后输出答案区间的值

最经典基础的区间DP

#include <bits/stdc++.h> using namespace std; using ull =unsigned long long; const int N=305; const int INF=0x3f3f3f3f; int n; int dp[N][N],a[N],sum[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n; memset(dp,INF,sizeof(dp)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; dp[i][i]=0; } for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r=l+len-1; for(int k=l;k<r;k++){ dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]); } } } cout<<dp[1][n]; return 0; }

下面有些名都是我自己瞎起的

环的处理

#include <bits/stdc++.h> using namespace std; using ll =long long; const int N=305; const int INF=0x3f3f3f3f; int n; int dp1[N][N],dp2[N][N],a[N],b[N],sum[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n; memset(dp2,0,sizeof(dp2)); for(int i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } for(int i=1;i<=2*n-1;i++){ b[i]=a[i+1]; } b[2*n]=a[1]; for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=2*n;l++){ int r=l+len-1; for(int k=l;k<r;k++){ dp2[l][r]=max(dp2[l][r],dp2[l][k]+dp2[k+1][r]+a[l]*a[k+1]*b[r]); } } } int ans2=0; for(int i=1;i<=n;i++)ans2=max(ans2,dp2[i][i+n-1]); cout<<ans2; return 0; }

逆向区间DP

这是一个逆向的区间DP，区间DP都是大区间通过小区间合并，但是这个题区是在逐步减小，我们可以这样考虑，将m个犯人，当作空牢房，放进去要给左右连续牢房的犯人吃肉，求怎么放最小价值，这样就变成了一个线形石子合并，合并代价为左右相邻连续区间犯人数

#include <bits/stdc++.h> using namespace std; using ull =unsigned long long; const int N=305; const int INF=0x3f3f3f3f; int n,m; int dp[N][N],a[N],sum[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>m>>n; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ cin>>a[i]; } a[0]=0;a[n+1]=m+1; for(int len=1;len<=n;len++){//这里不一样：初始区间长度为1 for(int l=1;l+len-1<=n;l++){ int r=l+len-1; dp[l][r]=INF; for(int k=l;k<=r;k++){ dp[l][r]=min(dp[l][r],dp[l][k-1]+dp[k+1][r]+a[r+1]-a[l-1]-1-1); //左区间 右区间 合并代价=区间长度-1 } } } cout<<dp[1][n]; return 0; }

双端区间DP

这个题dp要多一个变量分为左边插入和右边插入，不分也可以（两个玩家博弈那个题）

初始状态长度为1的区间插入方法就一种，我当时有点疑惑为什么设[0]为1，其实无所谓反正不能都是1，要不就是两种插入方式了

设区间（l,r），他的插入可以是l或r，

1.若是l，上一个可以是l+1或r

2.若是r，上一个可以是l或r-1

大区间将满足条件的小区间合并就好了

#include <bits/stdc++.h> using namespace std; using ll = long long; const int N=2005; const int INF=0x3f3f3f3f; const int MOD=19650827; int n,m; int dp[N][N][2],a[N],sum[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ cin>>a[i]; dp[i][i][0]=1; } ll ans=0; for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r=l+len-1; if(a[l]<a[l+1])dp[l][r][0]+=dp[l+1][r][0]; if(a[l]<a[r])dp[l][r][0]+=dp[l+1][r][1]; if(a[r]>a[r-1])dp[l][r][1]+=dp[l][r-1][1]; if(a[r]>a[l])dp[l][r][1]+=dp[l][r-1][0]; dp[l][r][1]%=MOD; dp[l][r][0]%=MOD; } } cout<<(dp[1][n][0]+dp[1][n][1])%MOD; return 0; }

划分DP

f [ i ][ j ]表示将前i个值分成j段的最优解，枚举断点（最后一段的开头），顺序枚举所以我们已经得到前k个元素分成j-1段的最优解（k小于i），加上最后一段的情况，取枚举过程中的最优解即可

#include <stdio.h> #include <string.h> #include <algorithm> int m,k; int c[505], s[505]; int f[505][505]; inline void init() { memset(f, 127 / 3, sizeof f); scanf("%d %d", &m, &k); for (int i = 1; i <= m; ++i) { scanf("%d", &c[i]); s[i] = s[i - 1] + c[i]; f[1][i] = s[i]; } } inline void work() { for (int i = 2; i <= k; ++i) for (int j = 1; j <= m; ++j) for (int l = 1; l < j; ++l) if (std:: max(f[i - 1][l], s[j] - s[l]) < f[i][j]) f[i][j] = std:: max(f[i - 1][l], s[j] - s[l]); } inline void print(int i, int j) { if(j == 0) return; if(j == 1) { printf("1 %d\n",i); return ; } int p = i, q = c[i]; while(q + c[p - 1] <= f[k][m]) { q += c[p - 1]; --p; } print(p - 1, j - 1); printf("%d %d\n", p, i); } int main(void) { init(); work(); print(m, k); return 0; }

和上面的题基本一样，多了一个环的处理

#include <bits/stdc++.h> using namespace std; using ll = long long; const int N=105; const int INF=0x3f3f3f3f; const int MOD=19650827; int n,m; int dp1[N][N],dp2[N][N],a[N],b[N],sum[N]; // dp[i][j]代表前i个数字分成j份的最大（小）解 int mod(int k){ return ((k%10)+10)%10; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } int ans2=INF,ans1=-INF; for(int s=1;s<=n;s++){//感觉这个处理很清晰，枚举起始断点 int t=0; for(int i=s;i<=s+n-1;i++){ b[++t]=a[i];//生成当前的新链 sum[t]=sum[t-1]+b[t];//前缀和 } memset(dp1,0,sizeof(dp1)); memset(dp2,0x3f,sizeof(dp2)); for(int i=1;i<=n;i++){ dp1[i][1]=mod(sum[i]); dp2[i][1]=mod(sum[i]); } for(int i=1;i<=n;i++){ for(int j=2;j<=m;j++){ for(int k=j-1;k<i;k++){//j-1段包含的k个值 //dp[i][j]=各个断点分成j-1段的最优解*最后所有剩余元素构成的一整段的值 dp1[i][j]=max(dp1[i][j],dp1[k][j-1]*mod(sum[i]-sum[k])); dp2[i][j]=min(dp2[i][j],dp2[k][j-1]*mod(sum[i]-sum[k])); } } } ans1=max(ans1,dp1[n][m]); ans2=min(ans2,dp2[n][m]); } cout<<ans2<<endl<<ans1; return 0; }