CF1239E Turtle

Description

https://www.luogu.com.cn/problem/CF1239E

总结

为什么一点思路都没有呢？

要找性质。

从哪里开始找呢？

比如确定数的集合能否确定数的排列顺序。

还是需要多做题总结。

Solution

令第一行的前缀和为 $p_i$，第二行的后缀和为 $s_i$，则种排列所有的贡献为：$\max(p_i+s_i)$。

假设我们已经直到第一行和第二行的选的数的集合，那么一定是第一行从小到大排序，第二行从大到小排序。贪心显然。

再考虑转移点，也就是从哪里开始第一行转到第二行是可能对最大值产生影响的。

考虑每次移动转移点的增量 $w_i=a_i-b_{i-1}$，那么答案可以写为：$\max(a_1+\sum b+\sum_{j=2}^i w_j)$。

再观察到 $a$ 是不降的，$b$ 是不升的，所以 $w$ 一定不降。$w$ 一开始可能为负，所以转移点一定再 $i=1$ 或者 $i=n$。

题目也就转化为了选择把 $2n$ 个数分为两个大小为 $n$ 的集合，最小化 $\max(a_1+\sum b,b_n+\sum a)$。而 $a_1,b_n$ 我们可以先不管考虑枚举，也可以猜测到因为这两个一定要选，肯定是把最小的两个数放到这两个数上。

题目又变成了选择 $2n-2$ 个数分别两个大小为 $n-1$ 的集合，最小化 $\max(\sum a,\sum b)$。这里就可以直接 dp 了。而由于 $s=\sum a+\sum b$ 是确定的，只需要找到一个集合可以大于 $\lceil \dfrac{s}{2}\rceil$ 的第一个数。可以直接 $O(n^2\sum a)$ 暴力背包。

发现取值都是 $01$，考虑 bitset 优化，复杂度为 $O(\dfrac{n^2\sum a}{w})$。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 55
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int a[maxn],b[maxn],c[maxn],tot1,tot2;
bitset<2500005>f[51][26];
int n,N;
signed main(void){
    int i,j,k;
	read(n);
    for (i=1;i<=2*n;i++) read(a[i]);
    sort(a+1,a+1+2*n);
    reverse(a+1,a+1+2*n);
    int N=2*n-2,sum=0;
    f[0][0][0]=1;
    for (i=1;i<=N;i++) {
        sum+=a[i];
        for (j=0;j<=min(i,n-1);j++) {
            f[i][j]=f[i-1][j];
            if (j) f[i][j]|=(f[i-1][j-1]<<a[i]);
        }
    }
    int ans=0;
    for (i=(sum+1)/2;i<=sum;i++) if (f[N][n-1][i]) {ans=i;break;}
    i=N,j=n-1,k=ans;
    while (i) {
        if (f[i-1][j][k]) b[++tot1]=a[i],i--;
        else c[++tot2]=a[i],j--,k-=a[i],i--;
    }
    b[++tot1]=a[2*n-1];
    c[++tot2]=a[2*n];
    sort(b+1,b+1+tot1);
    sort(c+1,c+1+tot2);
    for (i=1;i<=tot1;i++) printf("%d ",b[i]);put();
    for (i=tot2;i>=1;i--) printf("%d ",c[i]);put();
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i