一、题目
二、解法
要放假了，今天下午真的有点水啊 \(...\)
首先有一个 \(\tt observation\)：如果确定了第一行填的数和第二行填的数，那么此种情况的最优解是第一行从小到大排列，第二行从大到小排列，否则可以通过交换逆序对使得答案下降。
那么问题变成了决策每个数在哪一个，设 \(pre_i/suf_i\) 分别为第一行的前缀和，第二行的后缀和。那么答案是 \(\max(pre_i+suf_{i+1})\)，但是显然这样在 \(dp\) 中是算不了代价的，所以也转移不了。
考虑利用每一行都有序的性质，稍微有点做题经验的人就知道这可以看成背包问题，每一行都是要先选小的数才能选大的数，那么最大值只能是全选第一行的数和第二行的数，所以只能在 \(i=1/n\) 时取最值。
那么现在代价就好算了，就是 \(a(1,1)+a(2,n)+\max(\sum_{i=2}^{n} a(1,i),\sum_{i=1}^{n-1}a(2,i))\)，显然的结论是 \(a(1,1)\) 和 \(a(2,n)\) 要取最小的两个数，然后那么 \(\max(...)\) 就用背包决策即可，设 \(dp[i][j][k]\) 为考虑到第 \(i\) 个数，第一行一共选了 \(j\) 个数，选出数的总和是 \(k\) 是否可能，最后让总和尽可能对半分即可。
使用 \(\tt bitset\) 优化 \(dp\)，时间复杂度 \(O(\frac{1}{w}n^2\sum a)\)
三、总结
那个存在先选小数再选大数的背包是老套路了，要记得结论并且能当成模型来套题。
本题最重要的一点是简化代价计算，比如取最大值的代价可以考虑会在那些地方取得，如果代价复杂 \(dp\) 是转移不动的。
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
const int M = 1300000;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,sum,a[51],b[M];bitset<M> dp[51][26];//100MB
void dfs(int n,int m,int i)
{
if(!m) return ;
if(dp[n-1][m][i])
{
dfs(n-1,m,i);
return ;
}
if(i>=a[n] && dp[n-1][m-1][i-a[n]])
{
b[a[n]]--;
dfs(n-1,m-1,i-a[n]);
printf(" %d",a[n]);
}
}
signed main()
{
n=read();m=n<<1;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) a[i+n]=read();
sort(a+1,a+1+m);
for(int i=3;i<=m;i++) b[a[i]]++,sum+=a[i];
dp[2][0]=1;
for(int i=3;i<=m;i++)
for(int j=0;j<n;j++)
{
dp[i][j]|=dp[i-1][j];
if(j) dp[i][j]|=dp[i-1][j-1]<<a[i];
}
int tmp=sum;sum/=2;
for(int i=sum;i>=0;i--)
if(dp[m][n-1][i])
{
printf("%d",a[1]);
dfs(m,n-1,i);
puts("");
for(int j=5e4;j>=0;j--)
while(b[j]--) printf("%d ",j);
printf("%d\n",a[2]);
return 0;
}
}