United We Stand
算法本质
思维
题目大意
给定n个元素，要求放入B C两个集合中，满足：
- 任意C集合元素非任意B集合元素的约数
- 两个集合非空
输出方案或者不可能。
思路推演
稍加模拟可知，若元素更大，则比不可能是约数，所以将最大的元素放入C集合即可（可能有多个最大的），全相等的情况则不可行。
Olya and Game with Arrays
算法本质
思维
题目大意
给定n个大小>=2的集合，每个集合至多进行一次操作：
- 将本集合的某个元素移动至另一集合
输出最大化后所有集合的最小值之和。
思路推演
稍加模拟可以发现，集合只能移除一个元素，所以他的最小值有3个可能：
- 自己最小的元素
- 自己第二小的元素（把自己最小的元素移出去了）
- 别人移动进来的更小元素
当然，上面3个选择中，自己第二小的元素肯定是相对的最大值，所以尽可能使得所有集合都能选择这个方案，但是总要有集合来承载最小元素，则选一个集合即可，挨个模拟一次即可。
Another Permutation Problem
算法本质
思维
题目大意
玩家需要给出长度n排列，输出最大化后的：$\sum_{i=1}^np_i*i - (\max_{j=1}^np_j*j)$
思路推演
稍加模拟，整个式子会发现比较缺乏贪心思路，即所谓的情况比较复杂，通常的解决方法有2种：
- dp
可以将问题化成小而重复的问题解决 - 假设已知某个信息（通常配合二分）
可以用复杂度换取多一个信息
当然这个题肯定只能二分，我们假设最大值为m，则可以看成这样：
- 有两个1~n元素的集合元素，答案为其两两相乘之和
-m，同时需要保证两两相乘<=m（这需要枚举n^2^个值）
然后只需要贪心从大到小，找合适的数就好了：
- 比如对于
n找到一个x，使得nx<=m，然后再去找n-1的，这是显然贪心思维可以验证正确的
通常来说，朴素的做可以用二分搞定，但是这样就O(n^3^logn)，复杂度堪忧，实际上是可以优化的：
每对数组合，我们仅通过更大的数来找更小的数，对于值x，其可选范围是[1~m/x]。
根据贪心思路，我们必须不断从n往下看。
举例1~10，m=28
首先可以贪心的选择10--2和9--3
对于8来说，其范围是[1~3]，所以只能选择1了：8--1和7--4
当然到最后5 6是必须有一个>m的数的，所以可以说这样是无解的，但是思路是清晰的，以m/n为起始，后面选择的元素要么相邻在左或右，可以用指针或者堆来稍加维护。总体复杂度O(n^3^)。
整体思考
其实个人感觉，这个题的难度有点大了，即使赛时想到这个方向也感觉不是C的难度。
当然过这么多，是因为打表打出来的，其形式如同：1 2 ... x-1 x n n-1 ... x+1。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
Maximum Monogonosity
算法本质
思维、dp
题目大意
给定数组a[] b[]和k，现在要求选择若干不相交的区间，要求：
- 区间长度之和为
k
[l, r]区间价值为| b[l]-a[r] | + | b[r]-a[l] | 。
输出最大化价值和。
n k <= 3e3思路推演
所谓情况复杂，基本需要使用dp。
构建一个朴素的dp[l][r][x]表示区间l~r中选择了长度总和为x最大值。
显然这个dp的空间复杂度、时间复杂度都是O(n^3^)，需要优化。
首先优化空间复杂度——dp[i][x]表示区间1~i中选择了长度总和为x`最大值。
什么情况需要用
[l][r]来表示l~r区间，什么情况可以优化至[i]来表示1~i区间。目前还没有实力能够总结，但是有一条可以实践的：
若能用[i]来表示，且无故障的，就可以用[i]
谨记我们的目标：优化转移复杂度，写出转移方程：
- $dp[i][j] = \max_{t=1}^{i}val[i-t+1][i] + dp[i-t][j-t]$ （最后的
i必选） - $dp[i][j] = max_{t=1}^{i-1}dp[t][j]$ （最后的
i不选，这个方程转移比较简单）
这个式子无法优化，将上式的val[][]继续拆解：
- $dp[i][j] = \max_{t=1}^{i}dp[i-t][j-t] + \max \begin{Bmatrix}+b[i]-a[i-t+1]+b[i-t+1]-a[i] \\+b[i]-a[i-t+1]-b[i-t+1]+a[i] \\-b[i]+a[i-t+1]+b[i-t+1]-a[i] \\-b[i]+a[i-t+1]-b[i-t+1]+a[i]\end{Bmatrix}$
- $dp[i][j] = max_{t=1}^{i-1}dp[t][j]$
上式第二个方程转移很简单，重点看第一个，抛开上式的a[i] b[i]，其他下标有着统一性，对于dp[i][i-x]来说，其希望有如下的预处理
- $\max_{t=x}^{i-1} \{dp[t][t-x] - a[t+1] + b[t+1]\}$
这个式子维护需要用x作为标识对上式添加b[i]-a[i]，这样就O(1)得到了转移方程第一个式子的最大值，我们同法炮制，得到了转移方程4个式子的最大值，再取max即可。
ac核心代码
细节说明：
pre[]数组默认值为-1e18是因为其可能为负数，dp则不可能为负数，所以直接给0即可- 4个
pre[]数组维护的都是i元素必选的情况，记得写上i元素不选的情况 j==0的预处理
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>k;
vector<int> a(n+5), b(n+5), pre1(n+5, -1e18), pre2(n+5, -1e18), pre3(n+5, -1e18), pre4(n+5, -1e18);
vector<vector<int>> dp(n+5, vector<int>(k+5, 0));
rep(i,1,n) cin>>a[i];
rep(i,1,n) cin>>b[i];
for (int i=0; i<=n; i++)
{
for (int j=0; j<=min(i, k); j++)
{
if (i>j) dp[i][j] = dp[i-1][j]; // 考虑第i个元素不选情况
int cha = i-j;
int v1 = pre1[cha] + b[i] - a[i];
int v2 = pre2[cha] + b[i] + a[i];
int v3 = pre3[cha] - b[i] - a[i];
int v4 = pre4[cha] - b[i] + a[i];
int val = max(max(v1, v2), max(v3, v4)); // 第i个元素必选情况的最大值
dp[i][j] = max(dp[i][j], val);
if (j==0) dp[i][j]=0; // 如果j==0，pre[]其实并未初始化，得到的值并不正确，所以手动处理为0
pre1[cha] = max(pre1[cha], dp[i][j]-a[i+1]+b[i+1]);
pre2[cha] = max(pre2[cha], dp[i][j]-a[i+1]-b[i+1]);
pre3[cha] = max(pre3[cha], dp[i][j]+a[i+1]+b[i+1]);
pre4[cha] = max(pre4[cha], dp[i][j]+a[i+1]-b[i+1]);
}
}
int ans = dp[n][k];
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)