Codeforces Round 889 (Div. 2)

C2.Dual (Hard Version)

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

D.Earn or Unlock

算法本质

思维、dp、bitset优化

题目大意

给定顺序n张卡牌，初始时玩家默认获得第一张卡牌（剩余的n-1张卡牌在牌堆）。
每张卡牌有数字x[i]，玩家的操作有且仅有两种方式使用手中的卡牌：

• 加分：消耗掉一张卡牌，积分增加x[i]
• 无中生有：消耗掉一张卡牌，获得牌堆最上方的x[i]张卡牌（若牌堆剩余数<x[i]，则全部拿走）

输出最大化的积分。

n <= 1e5
x[i] <= n

思路推演

贪心地想，什么情况能获得最多积分——手牌一定要用完，即拿到i张牌，得分是固定的：pre[i] - (i-1)。（pre[]是x[]的前缀和数组）
现在问题在于，如何鉴定是否能恰好抵达某个点。

手牌选择、价值、恰好抵达某个状态，这其实比较类似01背包，但是有所不同。

以上的题面稍显复杂，适合用dp，暂时抛弃复杂度的考虑，思考dp能否求得某个点是否能恰好抵达。
dp[i][j]表示使用前i张牌，能否恰好抵达j
转移方程也比较好写：

• 继承：dp[i][j] |= dp[i-1][j]
• 使用x[i]：dp[i][j] |= dp[i-1][j-x[i]]

但是同理，这样复杂度太高了，但是这又是布尔类型的dp，思考能否用bitset的位运算思想进行优化。

既然要用bitset优化复杂度，则必须以x[i]为单位，而非点：bit[]表示当前点能否恰好抵达。
于是自然得出了使用时的转移方程：bit |= bit<<x[i]，但是这样也存在问题，就是许多原本无法恰好变成了可行。

可以测试这组数据：
4
1 2 0 0
原本无法恰好拿3张牌，但是用以上的转移方程可行。

观察原因，发现本质是，是因为在对第i张牌做转移时，其bit[<i]的情况也会被转移，但是实际上那些情况都无法抵达i，就不存在说用x[i]作为手牌进行转移了。
所以只需要忽略前部分的即可，只需要每次转移后消除当前bit[i]的记录就好。

同时还有一个小问题，如果将所有卡牌都取完，拿得分不一定是pre[n]-(n-1)，考虑到x[i]的值<=n，所以可以将牌堆底部扩展n张x[]为0的卡牌，这样就能保证得分规则一定是pre[i]-(i-1)。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], pre[maxn];        
inline void solve()
{
    cin>>n;
    rep(i,1,n)    cin>>a[i], pre[i]=pre[i-1]+a[i];
    for (int i=n+1; i<=2*n; i++)    a[i]=0, pre[i]=pre[i-1]+a[i];    // 牌堆底部添加n张0价值卡牌
    bitset<200005> bit;        // bit[i]表示[1~i]个卡牌，能否有组合恰好抵达i位置
    bit.set(1);        // 系统免费送第一张卡牌
    int ans = 0;
    for (int i=1; i<=2*n; i++)
    {
        if (bit.test(i))        // 说明当前点可恰好达
            ans = max(ans, pre[i]-i+1);        // 则计算价值
        bit |= bit<<a[i];        // i-1回合可达的点，这次经过a[i]能达的更多点
        bit.reset(i);        // 删除当前的点的可达值，详细看题解解释
    }
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。