結果
問題 | No.1494 LCS on Tree |
ユーザー |
|
提出日時 | 2021-04-30 21:57:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 1,167 bytes |
コンパイル時間 | 871 ms |
コンパイル使用メモリ | 75,776 KB |
実行使用メモリ | 35,072 KB |
最終ジャッジ日時 | 2024-11-20 14:58:33 |
合計ジャッジ時間 | 3,624 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
コンパイルメッセージ
main.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 44 | main() | ^~~~
ソースコード
#include<iostream> #include<algorithm> #include<vector> using namespace std; int N; vector<pair<int,char> >G[2000]; string S,T; int ans; int dpS[2000][2001],dpT[2000][2001]; void dfs(int u,int p) { for(pair<int,char>e:G[u]) { int v=e.first; if(v==p)continue; dfs(v,u); for(int k=0;k<=S.size();k++) { ans=max(ans,dpS[u][S.size()-k]+dpT[v][k]); ans=max(ans,dpT[u][S.size()-k]+dpS[v][k]); if(T[k]==e.second) { ans=max(ans,dpS[u][S.size()-k-1]+dpT[v][k]+1); } if(S[k]==e.second) { ans=max(ans,dpT[u][S.size()-k-1]+dpS[v][k]+1); } } for(int k=0;k<=S.size();k++) { dpS[u][k]=max(dpS[u][k],dpS[v][k]); if(S[k]==e.second)dpS[u][k+1]=max(dpS[u][k+1],dpS[v][k]+1); dpT[u][k]=max(dpT[u][k],dpT[v][k]); if(T[k]==e.second)dpT[u][k+1]=max(dpT[u][k+1],dpT[v][k]+1); if(k<S.size()) { dpS[u][k+1]=max(dpS[u][k+1],dpS[u][k]); dpT[u][k+1]=max(dpT[u][k+1],dpT[u][k]); } } } } main() { cin>>N>>S; T=S; reverse(T.begin(),T.end()); for(int i=1;i<N;i++) { int a,b;char c; cin>>a>>b>>c; a--,b--; G[a].push_back(make_pair(b,c)); G[b].push_back(make_pair(a,c)); } dfs(0,-1); cout<<ans<<endl; }