Ascending Photo Gym - 101623A（DP）

本文主要是介绍Ascending Photo Gym - 101623A（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
将一段数切成最少的段，使得可以将其重新拼起来序列不减。

思路：
感觉很难的一道题目，代码参考的wxh博客，思路的话可以参考这个博客。

我们先将所有数切开，一共n-1段，这样一定满足可以拼成递增序列。
我们再考虑将其中一些部分“接起来”，优化这个结果。
首先一开始就相同且相邻的数可以直接拼起来当做一个数，这个可以预处理出来。
所以可以拼起来的数就是大小相差为1（离散化过后的大小），且位置相邻。

则定义$f[i][j]$为考虑值小于等于$i$的部分，最后一次拼接的位置为$(j,j+1)$的最大拼接数。

转移的时候每次遍历同一个数的所有位置，唯一的限制就是要求两次合并不能在相连，除非中间那种数只有一个。
也就是 1 2 3 2，那么1 2合并和2 3合并是不可以的，因为后面那个2放不进来了。
而 1 2 3 1，则可以将1 2，2 3合并。

所以$f[i][j]=max(f[i-1][k]+1),k+1!=j或者(k+1=j且pos[i].size()==1)$
这样转移是n^2的，想办法优化。

可以发现这样的转移只依赖于上一层状态的最大值，如果最大值不满足约束条件，那么取次大值一定满足约束条件。所以我们只需要维护每一层状态的最大值与次大值就可以完成转移了，这样就优化成了O(n)。当然，算上离散化就是nlogn。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;int main() {int n;scanf("%d",&n);vector<int>a(n);for(int i = 0;i < n;i++) {scanf("%d",&a[i]);}vector<int>d = a;sort(d.begin(),d.end());d.erase(unique(d.begin(), d.end()),d.end()); //所有值vector<vector<int>>pos(d.size() + 1);  //每个值的位置vector<int>b; //离散去重的a数组for(int i = 0;i < n;i++) {a[i] = lower_bound(d.begin(), d.end(), a[i]) - d.begin();if(!b.empty() && a[i] == b.back()) {continue;}pos[a[i]].push_back(b.size());b.push_back(a[i]);}n = b.size();pair<int,int>f[2];f[0] = {0,n};f[1] = {0,n};for(int i = 0;i < d.size();i++) {pair<int,int>p[2];p[0] = f[0];p[1] = f[1];for(int j = 0;j < pos[i].size();j++) {int v = pos[i][j];if(v != n - 1 && b[v] + 1 == b[v + 1]) {pair<int,int>value;int x = 0,y = 0;if(f[0].second + 1 != v) {x = f[0].first + 1;} else {x = f[1].first + 1;}if(pos[i + 1].size() == 1) {y = n;} else {y = v;}value = {x,y};p[1] = max(p[1],value);if(p[1] > p[0]) {swap(p[1],p[0]);}}}f[0] = p[0];f[1] = p[1];}printf("%d\n",n - 1 - f[0].first);return 0;
}

这篇关于Ascending Photo Gym - 101623A（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---