Array Shrinking
思路：可以看出是區間dp的問題，n = 500，剛好可以是O（n^3），難點在于相鄰數字合并的維護，這里我們可以定義一個二維的陣列a[l][r]，表示L到R區間合并后的數字是a[l][r]，比如 3 3 3 a[1][2] = 4, a[2][3] = 4，然后dp[l][r]表示L到R的最短數列長度，容易想到當dp[l][mid-1]和dp[mid][r]等于1且a[l][mid-1] == a[mid][r]時，區間可以合并，可以推出狀態轉移方程：
①(dp[l][mid-1] == 1 && dp[mid][r] == 1 && a[l][mid-1] == a[mid][r]) dp[l][r] = 1, a[l][r] = a[mid][r] + 1;
②dp[l][r] = min(dp[l][mid_1 - 1] + dp[mid_1][r], dp[l][mid_2 - 1] + dp[mid_2][r]...);
#include <iostream> #include <cstdio> #include <algorithm> #include <functional> #include <set> #include <vector> #include <queue> #include <cstring> using namespace std; #define ll long long #define pb push_back #define fi first #define se second const int N = 2e5 + 10; const int INF = 1e9; const int MAX_DIS = 2e6; int _case = 0; void solve(){ int n; cin >> n; vector<vector<int > > num(n + 1, vector<int >(n + 1)); for(int i = 1; i <= n; ++i) cin >> num[i][i]; vector<vector<int > > dp(n + 1, vector<int >(n + 1, INF)); for(int i = 1; i <= n; ++i) dp[i][i] = 1; for(int len = 2; len <= n; ++len){ for(int l = 1; l <= n - len + 1; ++l){ int r = l + len - 1; for(int mid = l + 1; mid <= n; ++mid){ if(dp[l][mid - 1] == 1 && dp[mid][r] == 1 && num[l][mid - 1] == num[mid][r]){ dp[l][r] = 1; num[l][r] = num[mid][r] + 1; }else{ dp[l][r] = min(dp[l][r], dp[l][mid - 1] + dp[mid][r]); } } } } //cout << "ans ="; cout << dp[1][n] << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55348.html
標籤：其他
上一篇：資料結構（C語言版）---圖