终于还是走到了这一步已经很久没有更新过了转眼间就要大三了从当初差点埋葬在一些简单的算法题的时候到如今能比较好的阅读代码的地步实属不易。想起当初盼望着拿一个蓝桥杯省二省三的时候在今年也拿到了省一也在国赛拿了奖最后也进入了学校的acm实验室。这个暑假就再记录一下我的算历程因为一直在复习期末现在就从一些比较简单的题目入手热下身也方便我之后回顾这些题目就懒得手写了。1.P2858 [USACO06FEB] Treats for the Cows G/S1理清思路选择方法这题属于基础的区间dp类型最开始还觉得能通过暴力解决把最大的留在最后加上就行了可惜是错的。反证贪心的不成立情况:6 9 9 9 9 1 10 这样会使得1使用了一个很大的权值在倒数第二个被加上去正确的是把10、1先取走。而dp算法的核心就是先找最后一个然后再扩充。2dp起步工作其实dp的难点就是起步很多题明知道要用dp但是却无从下手在上文也说了先找最后一个再扩展那么我们就设一个二维dp[left][right]代表left~right之间的最大值。而起步就将初始值导入进去vector int v(n1); for(int i1;in;i) cin v[i]; for(int i1;in;i) { dp[i][i]1LL*v[i]*n; }dp容量较大定义在main外面。3开始延展经过2dp上我们已有了初始值然后让它们的区间范围从长度len1一直到长度lenn将大的保留下来单个小的插入进去最后慢慢形成最大的。外循环代表区间长度内循环代表起始位置。接下来展示完整代码。#include bits/stdc.h using namespace std; typedef long long ll; ll dp[2010][2010]; int main() { int n; cin n; vector int v(n1); for(int i1;in;i) cin v[i]; for(int i1;in;i) { dp[i][i]1LL*v[i]*n; } for(int len1;lenn;len) { for(int l1;llenn;l) { int rllen; dp[l][r]max(dp[l1][r]v[l]*(n-len),dp[l][r-1]v[r]*(n-len)); } } cout dp[1][n]; return 0; }这里巧妙的是不需要再设一个day的变量只需要用n和len的关系就可以解决。我还思考了一下如果从最初值开始算也就是dp初始值就是v[i]而不是v[i]*n的情况从1~n的方式解题但似乎不可以。2.P1435 [IOI 2000] 回文字串1理清思路选择方法正常情况下对于新手还是会以贪心的方法去解题但是这题会很简单的就判断出来无法利用贪心去找出有多少个需要插入的位置这不是普通的去判断是否为回文串的题目但是去使用区间dp却发现还是无从下手。怎么去起步怎么去构思、优化这是比较难想到的。2构建想法分清情况这道题没什么起步的说法因为每个小部分的初始值都可以视为0也就是当只有一个字符的时候无需插入任何字符使得其成为回文因为长度为1的时候就是回文。那么接下来我们就要是他延展出去什么时候要标记需要插入什么时候不需要。3用代码解决问题核心代码也是两个循环解决dp问题而需要考虑的情况就是两种。需要标记和不需要标记的情况1.不需要标记先从不需要标记下手比较好理解当区间的左右两边字符相等的时候可以视为不需要标记但是在它们中间还有需要标记的字符那我们必须将之前的标记次数赋值给现在的代码如下if(s[i]s[j]) { dp[i][j]dp[i1][j-1]; }2.需要标记的情况当我们已经解决了无需标记的情况了那我们就不需要考虑需要标记的情况了因为无非就是两边不相等的情况使用else即可我们需要构思的就是需要如何实现。实现方法当一个区间左右两边不相等的情况下我们取一个最小的标记值插入的次数而最小的就是去掉一个左或右端点然后把去掉端点后的区间的原始标记值1就等于我们所要求的答案了代码如下else { dp[i][j]min(dp[i1][j],dp[i][j-1])1; }完整代码如下#include bits/stdc.h using namespace std; int dp[1010][1010]; int main() { string s; cin s; int ns.size(); for(int len1;lenn;len) { for(int i0;ilenn;i) { int jilen; if(s[i]s[j]) { dp[i][j]dp[i1][j-1]; } else { dp[i][j]min(dp[i1][j],dp[i][j-1])1; } // cout dp[i][j] ; } // cout endl; } cout dp[0][n-1]; return 0; }当你想把其运行的每个步骤过程显示出来的话则可以把有斜杠的去掉以abdcb为例其每个区间的变化值如下3.P9325 [CCC 2023 S2] Symmetric Mountains找到区间dp的解题规律之后写这些题就会变得简单很多这里就不详细拆分了而且这题就只用考虑一种情况都是以找中心为核心考虑两边的差值即可往外循环扩散。详细代码如下#include bits/stdc.h using namespace std; typedef long long ll; ll dp[5010][5010]{0}; int main() { int n; cin n; vector ll peak(n); for(int i0;in;i) cin peak[i]; for(int len1;lenn;len) { ll mi5000*1e6; for(int i0;ilen-1n;i) { int jilen-1; dp[i][j]dp[i1][j-1]abs(peak[i]-peak[j]); if(dp[i][j]mi) midp[i][j]; } cout mi ; } return 0; }刚开始还会考虑区间长度为奇数偶数的情况后面发现好像不用这应该也是最优解了自己写出来了也没丢给ai了如果还有优解可以告知一下。4.P15896 [TOPC 2025] Palindromic Distance这题跟回文串的题目相似我本来就想以上面回文串的方式写这道题然后发现一个规律数据应该要向上整除2可惜这只是样例的还是没有考虑到位只能去看题解了其实想了下也挺简单的因为它能改变一个字符所以当两个不一样的时候不需要插入两次。代码如下#include bits/stdc.h using namespace std; typedef long long ll; int dp[3010][3010]{0}; int main() { int t; cin t; while(t--) { string s; cin s; int ns.size(); for(int len1;lenn;len) { for(int i0;ilenn;i) { int jilen; if(s[i]s[j]) { dp[i][j]dp[i1][j-1]; } else { dp[i][j]min({dp[i1][j],dp[i][j-1],dp[i1][j-1]})1; } } } int resdp[0][n-1]; cout resendl; } return 0; }这道题需要考虑的就是多一个dp[i1][j-1]的最小值算进去因为两边不一样可以改变一次就解决而且大多数就是这种情况。区间dp的简单题就分享到这接了下来需要冲刺几道较难的题目同时也记录一下随着时间和努力所收获的进步欢迎大佬讨论随时回复。