Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## map,vector飘过......

Posted by ZxyElf at 2013-02-18 23:46:53 on Problem 1952
```#include <iostream>
#include <vector>
#include <map>
using namespace std;

int dp[5001];
int value[5001];
int ans;
map<pair<int,int>,int> m;
vector<int> vec[66000];

int Max(int a,int b){
return (a>b)? a:b;
}

void GetAns(int n){
int cnt=0;
int D[5001];
for (int i=0;i<n;i++){
if (cnt &&  D[cnt]>value[i])
D[++cnt]=value[i],dp[i]=cnt;
else if (!cnt)
D[++cnt]=value[i],dp[i]=1;
else
{
int left=1,right=cnt,mid;
while (left<=right){
mid=(left+right)/2;
if (D[mid]<=value[i])
right=mid-1;
else
left=mid+1;
}
D[left]=Max(D[left],value[i]);
dp[i]=left;
}
}
ans=cnt;
}

int main()
{
int n,i,j;cin>>n;
for (i=0;i<n;i++) scanf("%d",value+i);
GetAns(n);
for (i=0;i<n;i++){
vec[value[i]].clear();
for (j=0;j<i;j++){
if (value[j]>value[i] && dp[j]==dp[i]-1){
if (  vec[value[i]].empty() || value[j]>vec[value[i]].back())
vec[value[i]].push_back(value[j]);
}
}
int size=vec[value[i]].size();
int temp=0;
for (j=0;j<size;j++) temp+=m[make_pair(vec[value[i]][j],dp[i]-1)];
if (dp[i]==1) {
if (m.find(make_pair(value[i],1))==m.end()) m.insert(make_pair(make_pair(value[i],1),1));
}else {
pair<int,int> p=make_pair(value[i],dp[i]);
if (m.find(p)==m.end()) m.insert(make_pair(p,temp));
else m[p]=temp;
}
}
int Cnt=0;
map<pair<int,int>,int> ::iterator e,End=m.end();
for (e=m.begin();e!=End;e++)
if (e->first.second==ans)
Cnt+=e->second;
cout<<ans<<' '<<Cnt<<endl;
return 0;
}

```

Followed by: