loj2538 「PKUWC 2018」Slay the Spire
pkusc 快到了……做点题涨涨 rp。
ref我好菜啊QAQ。
可以发现期望只是一个幌子。我们的目的是：对于所有随机的选择方法（一共 \(\binom{2n}{m}\)种），这些选择方法都最优地打出 \(k\) 张牌，他们能造成的伤害的和是多少。
显然的是，能打强化就打强化（不过你好歹也要攻击一张）。记 \(m\) 张卡中分给强化卡的数量为 \(i\)。我们枚举 \(i\)，根据 \(i\) 与 \(k\) 的大小关系来决定怎样打牌。
那么 \(i < k\) 时，就打出 \(i\) 张强化卡，\(k-i\) 张攻击卡。（这意味着你能打的强化卡总共才 \(i\) 张，当然是能打强化卡就打强化卡）
\(i \geq k-1\) 时，就打出 \(k-1\) 张强化卡，\(1\) 张攻击卡。（这意味着你能打的强化卡还挺多，留一张攻击就行了）。
记 \(F(i,j)\) 为分给强化卡的数量为 \(i\)，打出 \(j\) 张，所有方案翻的倍率的和。\(G(i,j)\) 为分给攻击卡的数量为 \(i\)，打出 \(j\) 张，所有方案的（不加强化的）攻击力和。
两者分别对应 \(F(i,i) \times G(m-i,k-i)\) 和 \(F(i,k-1) \times G(m-i,1)\)。为什么可以是这种“和乘和”的形式呢？因为乘法分配律。
现在的问题变成快速计算 \(F\) 和 \(G\)。
关于 \(F\)，可以 sort 以后定义一个 \(f\)，\(f(i,j)\) 表示选（注意是选，不是分）了 \(i\) 张强化牌且最这 \(i\) 张牌中位置靠前的那张牌是所有强化牌中的第 \(j\) 个，这样的所有方案翻的倍率的和。转移看代码。\(G\) 和 \(g\) 也类似。
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int mod=998244353;
int T, n, m, k, a[1505], b[1505], c[3005][3005], f[1505][1505];
int g[1505][1505], sum[1505];
int F(int x, int y){if(x>T;for(int i=0; i<=3000; i++){c[i][0] = 1;for(int j=1; j<=i; j++)c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;}while(T--){memset(f, 0, sizeof(f));memset(g, 0, sizeof(g));scanf("%d %d %d", &n, &m, &k);for(int i=1; i<=n; i++) scanf("%d", &a[i]);for(int i=1; i<=n; i++) scanf("%d", &b[i]);sort(a+1, a+1+n);//跟牌的顺序无关，可以sortsort(b+1, b+1+n);for(int i=1; i<=n; i++){f[1][i] = a[i];//初始化f[][]，显然只选1张的倍率之和是a[i]sum[i] = (sum[i-1] + a[i]) % mod;//前缀和，方便转移}for(int i=2; i<=n; i++){for(int j=1; j<=n-i+1; j++)f[i][j] = (ll)a[j] * (sum[n]-sum[j]+mod) % mod;//打了i张牌，最前头的是第j张，那它就是f[i-1][j+1..n]的和再乘上第j号元素。这个转移的思想是枚举在打了i-1张牌的时候最前头的是哪一张for(int j=1; j<=n; j++)sum[j] = (sum[j-1] + f[i][j]) % mod;}for(int i=1; i<=n; i++){g[1][i] = b[i];sum[i] = (sum[i-1] + b[i]) % mod;}for(int i=2; i<=n; i++){for(int j=1; j<=n-i+1; j++)g[i][j] = ((ll)b[j]*c[n-j][i-1]%mod+(sum[n]-sum[j]+mod)%mod) % mod;//打了i张牌，最前头的是第j张。注意g代表的是（不加强化的）攻击力和。在这种情况下，打了i-1张牌的总情况是c[n-j][i-1]种（j+1..n中选i-1个的方案数），这是第一项；第二项就是继承自g[i-1][j+1..n]for(int j=1; j<=n; j++)sum[j] = (sum[j-1] + g[i][j]) % mod;}int ans=0;for(int i=0; i 转载于:https://www.cnblogs.com/poorpool/p/9065598.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！