2022浙江工商大学acm校赛总结

开局首先乱开选到了炸弹题，快速想了个bfs搞法后就开始写了，连wa三发之后发现不对劲，仔细想了一下发现思路是假的，这个时候已经半个小时了，榜上两个签到题已经被过穿，我还只有一个-3，开局稀碎

然后选择先把代码存起来去写签到，回文子序列属于经典的那种cfA题，平时会打cf的新生写这个应该不需要5分钟（

质因数分解题 我还稍微卡了一会 数学属实是碰的太少了

搞完两个签到回去搞炸弹题，重新想了一下发现是个缩点，抄一波tarjian板子过掉

然后就开始了大寄特寄的0号题，一个sb最短路+路径计数，硬是找不到wa点，造的数据都过，交上去全是wa。再结合这个题目描述（直观看起来是无向图但是没有明说；边权只写了上限没有写下界；数据规模允许 $n^2$），总之存在诸多疑点，那么dij换成spfa试了试，无向图改有向图试试，同时改试试… 于是对 $n$ 项疑点开始 $2^n$ 爆搜式提交，然而都没有过（我现在还不知道为什么wa）

此时的情况非常不妙，这个0号题已经过了十几个人了，差不多是所有大二三 + 一些新生，感觉非常危，但硬wa也没什么办法，于是弃题去搞别的了

很快发现取石子是个诈骗题，直接输出Alice，没关同步流还T一发

然后发现一棵刻入DNA的线段树，快速切掉没有什么压力

接着是那个函数题，看错题目绕了一会，回过神来发现其实开个优先队列乱搞就行了，$nlogn$ 没有什么问题

到这个时候差不多还有四十分钟，我做了个错误的决定：继续回去卡那个最短路…于是又是交了一堆wa，中途简单看了一下字符串题和dp题，字符串题面稀碎，没读明白；dp题想了个有点复杂的搞法，感觉时间来不及而且不一定对，就回去wa最短路了…一直wa到比赛结束，最后-19没搞出来，但场上一共过了差不多20个，快变成签到了。

最后6题rk3，没打过大一爷，非常不满意（寄，主要是该写出来的没写出来

总结一下，感觉心态还有点问题，一wa就容易乱交，另外弃题弃的不够彻底，dp题不一定能搞出来，但那个字符串，稍微花点时间读明白的话就会发现是个sb字典树，最后时间不重新回去卡最短路的话，这个也应该能出来（虽然出来了还是打不过大一爷，orz

补题：

Dwendwen给大佬分组

众所周知，实验室的同学们都是大佬。现在实验室共有N位大佬，为了发挥大佬们的辐射能力，Dwendwen准备按座位将其分为k个学习小组。

为了简化问题，我们假设实验室的座位是一种长度为N（N个座位）的线状结构，坐在第i个位置的大佬有影响力ai。在不能调整座位的前提下，Dwendwen需要将大佬们分为k组，其中每个组内的大佬都是座位连续的。一个小组的战斗力为小组所有大佬中，最大影响力与最小影响力之差，即max(a)-min(a)。

现在Dwendwen希望让实验室k个小组的总战斗力最大化，你能帮帮他吗？

Input:

第一行为两个空格分割的整数N(1≤N≤10000)和k(1≤k≤N)，分别表示实验室人数和小组个数。

第二行为N个空格分割的正整数，第i个数字ai(1≤ai≤500000)为坐在第i个位置的大佬的影响力。

Output:

实验室所有小组的总战斗力的最大值。

Sample Input:

5 1
2 4 5 6 3

Sample Output:

4

先是朴素的 $n^3$ dp做法，$dp[i][j]$ 表示前 $i$ 个数，分成 $j$ 组的最大答案

转移有 $dp[i][j] = dp[k][j-1]+max(a[k+1..i])-min(a[k+1..i])$，枚举这个 $k$

第一反应是拿某种单调队列来优化掉这一维 $k$，但是比较难搞

题解给了个不错的思路：放宽解空间

也就是说，我们可以把题意转换一下，转换后多了一些无意义的解，并不影响答案，但是能让优化变得更简单

本题的权值是 $max-min$，典中典，我们可以把它改成任意两数相减，显然最大的结果仍然是 $max-min$

那么转移时，考虑新加进来的 $a[i]$ 的成分：

• 不参与加减运算，$dp[i][j] = dp[i-1][j]$
• 作为被减数，$dp[i][j] = dp[k][j-1]+a[k+1]-a[i]$，这里相当于在枚举减数
• 作为减数，$dp[i][j]=dp[k][j-1]+a[i]-a[k+1]$，相当于枚举被减数

可以发现，我们只需要知道 $dp[k][j-1]+a[k+1]$ 的最大值，以及 $dp[k][j-1]-a[k+1]$ 的最大值，就能做到 $O(1)$ 转移了

这两个值沿途记录一下即可，不难维护。

---

再写另一种理解方式：

原题中，一个区间的权值是 $max-min$，那么可以发现，如果一个区间的边界元素不是其最大或最小值，那么把这个边界元素丢给隔壁区间一定不会更差。

所以最后我们其实是把整个数组分成了两种区间：两端分别是极大极小值的区间，和放哪都一样的区间（可以忽略的区间）

那么 $dp$ 转移的思路也比较清晰了（dp含义和上文相同）：

• 当前元素不是区间的边界（在区间内部或者被忽略），$dp[i][j] = dp[i-1][j]$
• 当前元素是区间边界，且是极小值，$dp[i][j] = dp[k][j-1]+a[k+1]-a[i]$
• 当前元素是区间边界，且是极大值，$dp[i][j]=dp[k][j-1]+a[i]-a[k+1]$

就和上面的转移方程是一样的。

最后，这个题的数据范围是 $10^4$，滚动数组优化一下空间。

int n, m;
int a[maxn];

ll f[10003][2];
void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    int mxa = a[1], mia = a[1];
    for(int i=1;i<=n;i++){
        mxa = max(mxa, a[i]);
        mia = min(mia, a[i]);
        f[i][1] = mxa - mia;
    }
    for(int k=2;k<=m;k++){
        int nw = k % 2;
        f[k-1][nw] = 0;
        ll mx = f[k-1][nw^1] + a[k], mi = a[k] - f[k-1][nw^1];
        for(int i=k;i<=n;i++){
            f[i][nw] = max({f[i-1][nw], mx - a[i], a[i] - mi});
            mx = max(mx, f[i][nw^1] + a[i+1]);
            mi = min(mi, a[i+1] - f[i][nw^1]);
        }
    }
    cout << f[n][m%2] << '\n';
}