luogu P2123 皇后游戏

传送门

跟国王游戏一样的分析

考虑相邻的两个大臣,设他们前面的(sum a_j)为(s),同时注意到后面人的贡献更大

所以(i)在前面时,(c_j=max(max(c_{last},s+a_i)+b_i,s+a_i+a_j)+b_j)

(j)在前面时,(c_i=max(max(c_{last},s+a_j)+b_j,s+a_i+a_j)+b_i)

如果最优方案里(i)在(j)前面,则刚才的(c_j<c_i)

即$$max(max(c_{last},s+a_i)+b_i,s+a_i+a_j)+b_j<max(max(c_{last},s+a_j)+b_j,s+a_i+a_j)+b_i$$$$max(c_{last}+b_i+b_j,s+a_i+b_i+b_j,s+a_i+a_j+b_j)<max(c_{last}+b_j+b_i,s+a_j+b_j+b_i,s+a_i+a_j+b_i)$$$$max(a_i+b_i+b_j,a_i+a_j+b_j)<max(a_j+b_j+b_i,a_i+a_j+b_i)$$$$max(b_i,a_j)+a_i+b_j<max(b_j,a_i)+a_j+b_i$$$$max(a_j,b_i)-a_j-b_i<max(a_i,b_j)-a_i-b_j$$
这时左右两边分别等价于(-min(a_j,b_i),-min(a_i,b_j)),进一步化简得(min(a_i,b_j)<min(a_j,b_i))

然后直接这样做就可以了

吗?

其实布星,这个条件不满足传递性,导致可能多次交换后使得后面结果变大 具体是什么我也讲不清

观察条件(min(a_i,b_j)<min(a_j,b_i)),这是要我们把(a)小的,(b)大的放前面,同时考虑(a,b)大小关系

对于所有(a<b)的,就按(a)升序排序

对于所有(a>b)的,就按(b)降序排序

(a=b)好像是用脚随便放( 就直接和第一种情况合并救星了

对于所有情况,考虑(a_i<b_i a_j>b_j),根据(min(a_i,b_j)<min(a_j,b_i)),则显然是把(a<b)的放在(a>b)的之前

总结:记(d_i=min(a_i,b_i))然后对三元组({a_i,b_i,d_i})按(d_i)升序排序,然后如果(a_i=d_i)放前面,否则放后面

#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define eps (1e-5)

using namespace std;
const int N=20000+10;
il LL rd()
{
    re LL x=0,w=1;re char ch;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
struct nn
{
  int d,a,b;
  bool operator < (const nn &bb) const {return d<bb.d;}
}z[N];
LL n,a[N],b[N],c[N];

int main()
{
  int T=rd();
  while(T--)
    {
      n=rd();
      for(int i=1;i<=n;i++)
        {
          int x=rd(),y=rd();
          z[i].a=x,z[i].b=y,z[i].d=min(x,y);
        }
      sort(z+1,z+n+1);
      for(int i=1,l=1,r=n;i<=n;i++)
        {
          if(z[i].d==z[i].a) a[l]=z[i].a,b[l]=z[i].b,++l;
          else a[r]=z[i].a,b[r]=z[i].b,--r;
        }
      c[1]=a[1]+b[1];
      LL su=a[1];
      for(int i=2;i<=n;i++)
        {
          su+=a[i];
          c[i]=max(c[i-1],su)+b[i];
        }
      printf("%lld
",c[n]);
    }
  return 0;
}