「PKUWC2018」Slay the Spire

题目链接

题意分析

这个题其实不是期望

就是一共有\(C_{2n}^m\)种情况 每一种情况选择\(k\)张牌 然后求最大攻击值的总和

我们考虑

当前抽出了选出了\(i\)张强化牌 \(m-i\)张攻击牌

首先 可以肯定的是 能出强化牌就尽量出强化牌

我们去枚举\(i\)

如果\(i 那么就出\(i\)张强化牌 \(m-i\)张攻击牌

如果\(i≥k\) 那么就出\(k-1\)张强化牌 \(1\)张攻击牌

\(CDY(i,j)\)表示i张强化牌出\(j\)张 所有方案强化的倍率之和

\(WZY(i,j)\)表示i张攻击牌出\(j\)张 所有方案强化的攻击力之和

二者分别对应\(CDY(i,i)* WZY(m-i,k-i)\)以及\(CDY(i,k-1)* WZY(m-i,1)\)

根据乘法分配律

现在考虑如何计算 \(CDY\)以及\(WZY\)

首先 对于相同数量的牌 由于跟顺序没有关系 所以我们\(sort\)之后贪心选择最大即可

\(f(i,j)\)表示选了\(i\)张强化牌并且最靠前的是第\(j\)张牌

同理 \(g(i,j)\)同理

详细见代码

CODE：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x7fffffff
#define N 3010
#define IL inline
#define M 1510
#define D double
#define mod 998244353
#define R register
using namespace std;
templateIL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
    _=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int T,n,m,k,ans;
int cdy[M],wzy[M];
int C[N][N];
int dp[M][M][2],sum[M];
IL int CDY(int x,int y)
{
	if(x

HEOI 2019 RP++

DP

相关

DP决策优化小结

dp专题练习

腾讯云搭建个人博客wordpress

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

Java高并发，ThreadPoolExecutor线程池技术

sqlserver with(NOLOCK) 或 with(READPAST）

单调队列优化DP历险记

CS5262设计DP转HDMI 4K60HZ +VGA 1080P方案芯片

「NOI2020」命运（树形DP+线段树合并）

线程池ThreadPool知识碎片和使用经验速记

阿里面试官常问的TCP和UDP，你真的弄懂了吗？

标签