結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー |
![]() |
提出日時 | 2015-05-15 23:31:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,413 bytes |
コンパイル時間 | 904 ms |
コンパイル使用メモリ | 99,200 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 04:18:19 |
合計ジャッジ時間 | 1,500 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 5 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:84:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 84 | scanf("%d", &t); | ~~~~~^~~~~~~~~~ main.cpp:86:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 86 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:88:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 88 | scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<vector>#include<list>#include<deque>#include<queue>#include<map>#include<set>#include<stack>#include<cmath>#include<sstream>#include<fstream>#include<iomanip>#include<ctime>#include<complex>#include<functional>#include<climits>#include<cassert>#include<iterator>using namespace std;int t;int n;#define MAX 102int a[MAX];vector<pair<int, int> > v[MAX]; //cost,goint use[MAX][MAX];int dp[MAX][MAX];int u_s = 0;int ind;inline void dfs(int aa, int b){if (use[aa][b]==u_s){return;}use[aa][b] = u_s;dp[aa][b] = 0;if (aa == b){ind = v[aa].size();}else{int pre = a[b] - a[aa];ind = lower_bound(v[aa].begin(), v[aa].end(), make_pair(pre, -1)) - v[aa].begin();}ind--;for (int i = ind; i >= 0; i--){if (use[v[aa][i].second][b] != u_s){dfs(v[aa][i].second, aa);}dp[aa][b] = max(dp[aa][b], dp[v[aa][i].second][aa]);}dp[aa][b]++;}int dp2[MAX][MAX];inline void dfs2(int aa, int b){if (use[aa][b]==u_s){return;}use[aa][b] = u_s;dp2[aa][b] = 0;if (aa == b){ind = v[aa].size();}else{int pre = a[b] - a[aa];ind = lower_bound(v[aa].begin(), v[aa].end(), make_pair(pre, -1)) - v[aa].begin();}ind--;for (int i = ind; i >= 0; i--){if (use[v[aa][i].second][b] != u_s){dfs2(v[aa][i].second, aa);}dp2[aa][b] = max(dp2[aa][b], dp2[v[aa][i].second][aa]);}dp2[aa][b]++;}int main(){scanf("%d", &t);while (t--){scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d", &a[i]);}for (int i = 0; i < n; i++){v[i].clear();}for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){if (a[i] > a[j]){v[i].push_back(make_pair(a[i] - a[j], j));}}}for (int i = 0; i < n; i++){sort(v[i].begin(), v[i].end());}u_s++;for (int i = 0; i < n; i++){dfs2(i, i);}for (int i = 0; i < n; i++){v[i].clear();}for (int i = 0; i < n; i++){for (int j = i - 1; j >= 0; j--){if (a[i]>a[j]){v[i].push_back(make_pair(a[i] - a[j], j));}}}for (int i = 0; i < n; i++){sort(v[i].begin(), v[i].end());}u_s++;int maxt = 1;for (int i = 0; i < n; i++){dfs(i, i);maxt = max(maxt, dp[i][i] + dp2[i][i] - 1);}printf("%d\n", maxt);}return 0;}