Cities(2020昆明C)

Cities(2020昆明C)

题意：

给定长度为n的序列a[]，一次操作你可以选择一个数值相同的连续区间，将这个区间的数值修改为其他数。
问多少进行多少次操作能使得区间所有数相同。
n<=5000，每种a[i]最多出现15次

题解：

参考题解
很明显是数位dp，但是我二维状态推了一阵子没想出，又加了一维还是没搞明白
最后看到题解，发现这个状态转移确实好
我们设dp[l][r]表示[l,r]变成相同颜色的最小操作次数
pre[i]表示在左边区间上一次出现a[i]的位置

我们先将数组b相邻相同的元素合并，得到数组a，此时数组a任意相邻均不重复
dp[l][r]状态转移:

因为现在任意两个相邻元素都不一样，所以多加一个元素，操作次数必然+1,所以有dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1

有个方法可以节省步骤，现在有区间[l,k],[k+1,r],如果$a[k]==a[j]$,此时我们将左边都染成k颜色，右边都染成j颜色，k和j又是一样的颜色，这样合并不用额外操作。dp[l][r]=min(dp[l][k]+dp[k+1][r])

最后d[1][n]就是答案.
tot为去掉相邻重复后的数组，因为每种a[i]最多出现15次，所以k最多也就是枚举15下
复杂度$O(15to{t}^2)$

代码：

// Problem: Cities // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/12548/C // Memory Limit: 524288 MB // Time Limit: 8000 ms // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 6000; int a[maxn]; int f[maxn][maxn]; int pre[maxn]; int last[maxn]; int b[maxn]; int main() {rd_test();int t;read(t);while (t--) {int n;read(n); // tot=0;for (int i= 1; i <= n; i++)read(b[i]);int tot=0;for (int i= 2; i <= n; i++) {if (b[i] == b[i - 1]) {continue;}else a[++tot]=b[i-1];}a[++tot]=b[n];n=tot; // for(int i=1;i<=n;i++)cout<<a[i]<<" "; // cout<<endl;memset(pre, 0, sizeof pre);memset(last, 0, sizeof last);memset(f, INF_int, sizeof f);for (int i= 1; i <= n; i++) {pre[i]= last[a[i]];last[a[i]]= i;}for (int i= 1; i <= n; i++)f[i][i]= 0;for (int len= 2; len <= n; len++) {for (int l= 1; l + len - 1 <= n; l++) {int r= l + len - 1;f[l][r]= min(f[l + 1][r], f[l][r - 1]) + 1;for (int k= pre[r]; k >= l; k= pre[k]) {f[l][r]= min(f[l][r], f[l][k] + f[k + 1][r]);}}}cout << f[1][n] << endl;}return 0;//Time_test(); }

总结

以上是生活随笔为你收集整理的Cities(2020昆明C)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。