企业官网建设流程全解析

终于还是走到了这一步，已经很久没有更新过了，转眼间就要大三了，从当初差点埋葬在一些简单的算法题的时候，到如今能比较好的阅读代码的地步，实属不易。想起当初盼望着拿一个蓝桥杯省二省三的时候，在今年也拿到了省一，也在国赛拿了奖，最后也进入了学校的acm实验室。这个暑假就再记录一下我的算历程，因为一直在复习期末，现在就从一些比较简单的题目入手，热下身，也方便我之后回顾这些题目，就懒得手写了。

1.P2858 [USACO06FEB] Treats for the Cows G/S

（1）理清思路，选择方法

这题属于基础的区间dp类型，最开始还觉得能通过暴力解决，把最大的留在最后加上就行了，可惜是错的。反证贪心的不成立情况:6 9 9 9 9 1 10 ，这样会使得1使用了一个很大的权值，在倒数第二个被加上去，正确的是把10、1先取走。而dp算法的核心，就是先找最后一个，然后再扩充。

（2）dp起步工作

其实dp的难点就是起步，很多题明知道要用dp但是却无从下手，在上文也说了，先找最后一个，再扩展，那么我们就设一个二维dp[left][right]，代表left~right之间的最大值。而起步就将初始值导入进去

vector <int> v(n+1); for(int i=1;i<=n;i++) cin >> v[i]; for(int i=1;i<=n;i++) { dp[i][i]=1LL*v[i]*n; }

dp容量较大，定义在main外面。

（3）开始延展

经过（2），dp上我们已有了初始值，然后让它们的区间范围从长度len=1一直到长度len=n，将大的保留下来，单个小的插入进去，最后慢慢形成最大的。外循环代表区间长度，内循环代表起始位置。接下来展示完整代码。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[2010][2010]; int main() { int n; cin >> n; vector <int> v(n+1); for(int i=1;i<=n;i++) cin >> v[i]; for(int i=1;i<=n;i++) { dp[i][i]=1LL*v[i]*n; } for(int len=1;len<n;len++) { for(int l=1;l+len<=n;l++) { int r=l+len; dp[l][r]=max(dp[l+1][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[i+1][j-1]; }

2.需要标记的情况，当我们已经解决了无需标记的情况了，那我们就不需要考虑需要标记的情况了，因为无非就是两边不相等的情况，使用else即可，我们需要构思的就是需要如何实现。实现方法：当一个区间左右两边不相等的情况下，我们取一个最小的标记值（插入的次数），而最小的就是去掉一个（左或右）端点，然后把去掉端点后的区间的原始标记值+1就等于我们所要求的答案了，代码如下：

else { dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; }

完整代码如下：

#include <bits/stdc++.h> using namespace std; int dp[1010][1010]; int main() { string s; cin >> s; int n=s.size(); for(int len=1;len<n;len++) { for(int i=0;i+len<n;i++) { int j=i+len; if(s[i]==s[j]) { dp[i][j]=dp[i+1][j-1]; } else { dp[i][j]=min(dp[i+1][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 i=0;i<n;i++) cin >> peak[i]; for(int len=1;len<=n;len++) { ll mi=5000*1e6; for(int i=0;i+len-1<n;i++) { int j=i+len-1; dp[i][j]=dp[i+1][j-1]+abs(peak[i]-peak[j]); if(dp[i][j]<mi) mi=dp[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 n=s.size(); for(int len=1;len<n;len++) { for(int i=0;i+len<n;i++) { int j=i+len; if(s[i]==s[j]) { dp[i][j]=dp[i+1][j-1]; } else { dp[i][j]=min({dp[i+1][j],dp[i][j-1],dp[i+1][j-1]})+1; } } } int res=dp[0][n-1]; cout << res<<endl; } return 0; }

这道题需要考虑的就是多一个dp[i+1][j-1]的最小值算进去，因为两边不一样可以改变一次就解决，而且大多数就是这种情况。

区间dp的简单题就分享到这，接了下来需要冲刺几道较难的题目，同时也记录一下随着时间和努力所收获的进步，欢迎大佬讨论，随时回复。