結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー |
![]() |
提出日時 | 2017-01-07 11:20:29 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 332 ms / 2,000 ms |
コード長 | 1,598 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 68,628 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-17 15:22:19 |
合計ジャッジ時間 | 2,320 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
ソースコード
#include <algorithm>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <vector>#define rep(i, n) for (int i = 0; i < (n); i++)#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)using namespace std;typedef long long int lli;lli MOD = 1000000007;int main(){//dp[i][j] = max(dp[j][k]+1)s.t A[j]-A[k] < A[i]-A[j]lli m;cin >> m;rep(G, m){lli a[105], b[105];lli n, dp[105][105] = {}, dp2[105][105] = {};cin >> n;rep(i, n){cin >> a[i];b[n - 1 - i] = a[i];}rep(i, n){dp[i][i] = 1;dp2[i][i] = 1;}rep(i, n) for (int j = i - 1; j >= 0; j--){rep(k, n){if (i > j && j >= k)if (a[j] - a[k] >= 0 && a[j] - a[k] < a[i] - a[j])dp[i][j] = max(dp[j][k] + 1, dp[i][j]);}}rep(i, n){for (int j = i - 1; j >= 0; j--)rep(k, n){if (i > j && j >= k)if (b[j] - b[k] >= 0 && b[j] - b[k] < b[i] - b[j])dp2[i][j] = max(dp2[j][k] + 1, dp2[i][j]);}}lli ans = 0;rep(i, n){rep(j, n) rep(k, n){if (i >= j && n - i - 1 >= k)ans = max(ans, dp2[n - i - 1][k] + dp[i][j] - 1);}}cout << ans << endl;}}