题意
给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("%lld\n",ans);
return 0;
}