Instantly share code, notes, and snippets.

# ctylim/yukicoder209.cpp Created Feb 24, 2016

What would you like to do?
yukicoder No.209
 #include #include #include #include #include #include #include #include #include #include #include #include #include #define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() #define mod 1000000007 #define inf 2000000007 #define mp make_pair #define pb push_back typedef long long ll; using namespace std; template inline void output(T a, int p) { if(p) cout << fixed << setprecision(p) << a << "\n"; else cout << a << "\n"; } // end of template void calc(vector &X, vector> &dp){ repd(i, 1, X.size()){ rep(j, i){ if (X[i] > X[j]) { dp[i][j]++; } rep(k, j){ if (X[j] > X[k] && X[j] - X[k] < X[i] - X[j]) { dp[i][j] = max(dp[i][j], dp[j][k] + 1); } } } } } int main() { cin.tie(0); ios::sync_with_stdio(0); // source code int Q; cin >> Q; rep(q, Q){ int N; cin >> N; vector A(N); vector> dp(N, vector(N, 1)); rep(i, N){ cin >> A[i]; } vector L(N, 0), R(N, 0); calc(A, dp); rep(i, N){ rep(j, N){ L[i] = max(L[i], dp[i][j]); } } reverse(all(A)); dp.assign(N, vector(N, 1)); calc(A, dp); rep(i, N){ rep(j, N){ R[i] = max(R[i], dp[i][j]); } } int ret = 0; rep(i, N){ ret = max(ret, L[i] + R[N - i - 1] - 1); } output(ret, 0); } return 0; }
to join this conversation on GitHub. Already have an account? Sign in to comment