這道題還可以轉(zhuǎn)化成最長回文串，實(shí)際的答案是?離散化后的數(shù)組最長回文串切成一半有幾個數(shù)字，這些數(shù)字就是中間的數(shù)字需要對齊的對象，所以不用改變

#include <bits/stdc++.h> using namespace std;const int maxN = 5008;int n; int dp[maxN][maxN]; vector<int> a(1), b; vector<int> ans;void input() {cin >> n;for (int i = 0; i < n; i++) {int x; cin >> x;if (x != a.back()) a.push_back(x);}n = a.size() - 1;b = a;reverse(b.begin() + 1, b.end()); }void solve() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (a[i] == b[j]) {dp[i][j] = dp[i-1][j-1] + 1;}else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}} }void output() {cout << n - (dp[n][n] + 1)/2 << '\n'; }int main() {input();solve();output();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lishengkangshidatiancai/p/10362537.html

總結(jié)

以上是生活随笔為你收集整理的1114D . Flood Fill的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。