区间DP。

区间DP就是dp数组维护区间范围内的要求值大区间值与小区间有关最后输出答案区间的值最经典基础的区间DP#include bits/stdc.h using namespace std; using ull unsigned long long; const int N305; const int INF0x3f3f3f3f; int n; int dp[N][N],a[N],sum[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cinn; memset(dp,INF,sizeof(dp)); memset(sum,0,sizeof(sum)); for(int i1;in;i){ cina[i]; sum[i]sum[i-1]a[i]; dp[i][i]0; } for(int len2;lenn;len){ for(int l1;llen-1n;l){ int rllen-1; for(int kl;kr;k){ dp[l][r]min(dp[l][r],dp[l][k]dp[k1][r]sum[r]-sum[l-1]); } } } coutdp[1][n]; return 0; }下面有些名都是我自己瞎起的环的处理#include bits/stdc.h using namespace std; using ll long long; const int N305; const int INF0x3f3f3f3f; 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); cinn; memset(dp2,0,sizeof(dp2)); for(int i1;in;i){ cina[i]; a[in]a[i]; } for(int i1;i2*n-1;i){ b[i]a[i1]; } b[2*n]a[1]; for(int len2;lenn;len){ for(int l1;llen-12*n;l){ int rllen-1; for(int kl;kr;k){ dp2[l][r]max(dp2[l][r],dp2[l][k]dp2[k1][r]a[l]*a[k1]*b[r]); } } } int ans20; for(int i1;in;i)ans2max(ans2,dp2[i][in-1]); coutans2; return 0; }逆向区间DP这是一个逆向的区间DP区间DP都是大区间通过小区间合并但是这个题区是在逐步减小我们可以这样考虑将m个犯人当作空牢房放进去要给左右连续牢房的犯人吃肉求怎么放最小价值这样就变成了一个线形石子合并合并代价为左右相邻连续区间犯人数#include bits/stdc.h using namespace std; using ull unsigned long long; const int N305; const int INF0x3f3f3f3f; int n,m; int dp[N][N],a[N],sum[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cinmn; memset(dp,0,sizeof(dp)); for(int i1;in;i){ cina[i]; } a[0]0;a[n1]m1; for(int len1;lenn;len){//这里不一样初始区间长度为1 for(int l1;llen-1n;l){ int rllen-1; dp[l][r]INF; for(int kl;kr;k){ dp[l][r]min(dp[l][r],dp[l][k-1]dp[k1][r]a[r1]-a[l-1]-1-1); //左区间 右区间 合并代价区间长度-1 } } } coutdp[1][n]; return 0; }双端区间DP这个题dp要多一个变量分为左边插入和右边插入不分也可以两个玩家博弈那个题初始状态长度为1的区间插入方法就一种我当时有点疑惑为什么设[0]为1其实无所谓反正不能都是1要不就是两种插入方式了设区间l,r他的插入可以是l或r1.若是l上一个可以是l1或r2.若是r上一个可以是l或r-1大区间将满足条件的小区间合并就好了#include bits/stdc.h using namespace std; using ll long long; const int N2005; const int INF0x3f3f3f3f; const int MOD19650827; int n,m; int dp[N][N][2],a[N],sum[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cinn; memset(dp,0,sizeof(dp)); for(int i1;in;i){ cina[i]; dp[i][i][0]1; } ll ans0; for(int len2;lenn;len){ for(int l1;llen-1n;l){ int rllen-1; if(a[l]a[l1])dp[l][r][0]dp[l1][r][0]; if(a[l]a[r])dp[l][r][0]dp[l1][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; }划分DPf [ 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 N105; const int INF0x3f3f3f3f; const int MOD19650827; 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); cinnm; for(int i1;in;i){ cina[i]; a[in]a[i]; } int ans2INF,ans1-INF; for(int s1;sn;s){//感觉这个处理很清晰枚举起始断点 int t0; for(int is;isn-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 i1;in;i){ dp1[i][1]mod(sum[i]); dp2[i][1]mod(sum[i]); } for(int i1;in;i){ for(int j2;jm;j){ for(int kj-1;ki;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])); } } } ans1max(ans1,dp1[n][m]); ans2min(ans2,dp2[n][m]); } coutans2endlans1; return 0; }