hdu 5064 Find Sequence
一开始设想先排序然后两两相减并找出LIS来得到结果,显然没有考虑周全
根据题解,这题需要用到单调性DP。DP[i][j]表示序列以下标为i和j结尾,转移方程为
DP[i][j] = max(DP[k][i] + 1) { k<=i && num[j] - num[i] >= num[i] - num[k] }
但是直接求解时间复杂度为O(n^3)。该状态方程具有特殊性质,即
若 k 满足 { k<=i && num[j] - num[i] >= num[i] - num[k] } , 则 k 在 j+1 的情况下也满足。所以当计算 j+1 时,k 可直接从上一状态下继续进行。#include <stdio.h> #include <vector> #include <string> #include <algorithm> #include <queue> #include <cstring> #include <map> #include <set> #include <iostream> #include <cmath> using namespace std; #ifdef __GNUC__ typedef long long LL; inline void opt64(LL a) { printf("%lld", a); } #else typedef __int64 LL; inline void opt64(LL a) { printf("%I64d", a); } #endif const int MAXN = (1<<22)+5; const int MAXM = 2050; const double eps = 1e-10; const double PI = acos(-1.0); inline int cmp(const double x, const double y) { return ((x-y)>eps) - ((x-y)<-eps); } inline int cmp(const double x) { return ((x)>eps) - ((x)<-eps); } int n, m, mp[MAXN], mq[MAXM], cnt; int dp[MAXM][MAXM]; int solve() { int res = -1; if (n < 3) return n; sort(mp, mp+n); cnt = 0; mp[n] = -1; for (int i = 0, tp = 0; i< n; ++i) { tp++; if (mp[i] != mp[i+1]) { mq[cnt] = mp[i], dp[cnt][cnt] = tp, res = max(res,tp), tp = 0, ++cnt; } } for (int i = 0; i< cnt; ++i) { int k = i, ans = dp[i][i]; for (int j = i+1; j< cnt; ++j) { for (; k>=0 && mq[j]-mq[i]>=mq[i]-mq[k]; --k) { ans = max(ans, dp[k][i]); } dp[i][j] = ans+1; res = max(res, ans+1); } } return res; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i< n; ++i) scanf("%d", mp+i); printf("%d\n", solve()); } return 0; }