前置知识
解法
由于本题是 CF1628D1 Game on Sum (Easy Version) 的扩展，故先从 CF1628D1 Game on Sum (Easy Version) 讲解。
CF1628D1 Game on Sum (Easy Version)
设 \(x_{i}\) 表示第 \(i\) 轮时 Alice 选择的数。
设 \(f_{i,j}\) 表示已经进行了 \(i\) 轮，且使用了 \(j\) 次加法时的最大得分，状态转移方程为 \(f_{i,j}= \max \{ \min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i}) \}=\frac{f_{i-1,j}+f_{i-1,j-1}}{2}\)，边界为 \(\begin{cases} f_{i,0 \sim \infty}=0 & i=0 \\ f_{i,0}=0, f_{i,i}=i \times k & i \ne 0 \end{cases}\)。
- 由于
Bob想让结果尽可能小，所以有 \(f_{i,j}= \min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i})\)。 - 由于
Alice想让结果尽可能大，所以会让 \(\min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i})\) 取到最大值，即 \(f_{i-1,j}-x_{i}=f_{i-1,j-1}+x_{i}\) 时，解得 \(x_{i}= \frac{f_{i-1,j}-f_{i-1,j-1}}{2}\)，代入原式有 \(f_{i,j}=\frac{f_{i-1,j}+f_{i-1,j-1}}{2}\)。
由于 Bob 想让结果尽可能小，所以至多使用 \(m\) 次加法，故最终 \(f_{n,m}\) 即为所求。
另外，由于求解 \(f_{n,m}\) 的过程中只有加法和 \(\times \frac{1}{2}\) 运算，故可以将 \(k\) 缩小至 \(1\) 进行预处理 \(f_{n,m}\)，询问时再扩大到 \(k\)，即 \(f_{n,m} \times k\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
const ll p=1000000007;
ll f[2010][2010];
ll qpow(ll a,ll b,ll p)
{
ll ans=1;
while(b>0)
{
if(b&1)
{
ans=ans*a%p;
}
b>>=1;
a=a*a%p;
}
return ans;
}
int main()
{
ll t,n,m,k,i,j;
cin>>t;
for(i=1;i<=2000;i++)
{
f[i][0]=0;
f[i][i]=i;
for(j=1;j<=i-1;j++)
{
f[i][j]=((f[i-1][j]+f[i-1][j-1])%p)*qpow(2,p-2,p)%p;
}
}
for(i=1;i<=t;i++)
{
cin>>n>>m>>k;
cout<<f[n][m]*k%p<<endl;
}
return 0;
}
luogu P7137 [THUPC2021 初赛] 切切糕
从贪心的角度分析， Tinytree 的“优先选糕权”要尽量留给 \(a_{i}\) 较大的切糕，故需要先将 \(a\) 按照降序排序。
设第 \(i\) 块切糕 Kiana 切成的切糕大小为 \(x_{i}\) 和 \(a_{i}-x_{i}\)，规定有 \(x_{i} \ge a_{i}-x_{i}\)。
设 \(f_{i,j}\) 表示已经切了 \(i\) 块切糕，且使用了 \(j\) 次“优先选糕权”时 Tinytree 的最大总大小，状态转移方程为 \(f_{i,j}= \max \{ \min(f_{i-1,j}+a_{i}-x_{i},f_{i-1,j-1}+x_{i}),f_{i-1,j} \}=\max(\frac{f_{i-1,j}+f_{i-1,j-1}+a_{i}}{2},f_{i-1,j})\)，边界为 \(\begin{cases} f_{i,0 \sim \infty}=0 & i=0 \\ f_{i,0}=0, f_{i,i}=\frac{\sum_{j=1}^{i}a_{j}}{2} & i \ne 0 \end{cases}\)。
- \(x_{i}\) 的求解同 CF1628D1 Game on Sum (Easy Version) 。
- 由于算出的 \(x_{i}\) 可能使 \(a_{i}-x_{i}<0\) 成立，故最后需要与 \(f_{i-1,j}\) 取 \(\max\)。
由于 Tinytree 想让 Kiana 的总大小尽可能小，所以一定会使用 \(m\) 次“优先选糕权”，使自己的总大小尽可能大，故最终 \(\sum\limits_{i=1}^{n}a_{i}-f_{n,m}\) 即为所求。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
ll a[2510],sum[2510];
double f[2510][2510];
int main()
{
ll n,m,i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n,greater<ll>());
for(i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
for(i=1;i<=n;i++)
{
f[i][0]=0;
f[i][i]=1.0*sum[i]/2;
for(j=1;j<=i-1;j++)
{
f[i][j]=max((f[i-1][j]+f[i-1][j-1]+1.0*a[i])/2,f[i-1][j]);
}
}
printf("%.6lf",sum[n]-f[n][m]);
return 0;
}