gym102302E_Chi's performance
- 2019 年 11 月 7 日
- 筆記
题意
给n个二元组(v,p)，要求排序使得v从小到大，而且总价值最大，价值定义为相邻两个v值不同的p值之差绝对值之和。
分析
- in a row原来是相邻的意思。
- 对于每个相同v值的块来说，有用的数只有最大，次大，最小，次小，且如果块大小小于4，还有一些会重复，后面需要特判。
- 所以直接dp到每个块，左端点放哪个数，右端点放哪个数能获得的最大价值。
- 特判块大小为1的情况，以及上一个块大小为1的情况。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+50; struct node{ int v,p; bool operator<(const node& rhs)const{ if(v==rhs.v){ return p<rhs.p; }else{ return v<rhs.v; } } }a[N]; ll dp[N][5]; int mx[N][5],sz[N],num[N]; int n; vector<int> v; int main(){ // freopen("in.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].v,&a[i].p); v.push_back(a[i].v); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i<=n;i++){ a[i].v=lower_bound(v.begin(),v.end(),a[i].v)-v.begin()+1; } sort(a+1,a+1+n); int t=1; vector<int> tp; tp.push_back(a[1].p); for(int i=2;i<=n;i++){ if(a[i].v==a[i-1].v){ t++; tp.push_back(a[i].p); }else{ sz[a[i-1].v]=t; if(t>=2){ mx[a[i-1].v][3]=tp[t-1]; mx[a[i-1].v][2]=tp[t-2]; mx[a[i-1].v][1]=tp[1]; mx[a[i-1].v][0]=tp[0]; }else{ num[a[i-1].v]=a[i-1].p; } t=1; tp.clear(); tp.push_back(a[i].p); } } sz[a[n].v]=t; if(t>=2){ mx[a[n].v][3]=tp[t-1]; mx[a[n].v][2]=tp[t-2]; mx[a[n].v][1]=tp[1]; mx[a[n].v][0]=tp[0]; }else{ num[a[n].v]=a[n].p; } int vs=v.size(); for(int i=2;i<=vs;i++){ if(sz[i]==1){ for(int j=0;j<=3;j++){ if(sz[i-1]==1){ dp[i][j]=dp[i-1][0]+abs(num[i]-num[i-1]); }else{ for(int l=0;l<=3;l++){ dp[i][j]=max(dp[i][j],dp[i-1][l]+abs(num[i]-mx[i-1][l])); } } } }else{ if(sz[i-1]==1){ for(int j=0;j<=3;j++){ for(int k=0;k<=3;k++){ if(j==k || (sz[i]==2 && (j+k==2 || j+k==4)) || (sz[i]==3 && ( (j && k) && (j+k==3)))){ continue; } dp[i][j]=max(dp[i][j],dp[i-1][0]+abs(mx[i][k]-num[i-1])); } } }else{ for(int j=0;j<=3;j++){ for(int k=0;k<=3;k++){ if(j==k || (sz[i]==2 && (j+k==2 || j+k==4)) || (sz[i]==3 && ( (j && k) && (j+k==3)))){ continue; } for(int l=0;l<=3;l++){ dp[i][j]=max(dp[i][j],dp[i-1][l]+abs(mx[i][k]-mx[i-1][l])); } } } } } } ll ans=0; for(int i=0;i<=3;i++){ ans=max(ans,dp[vs][i]); } printf("%lldn",ans); return 0; }
