承担自己造的孽,好好学算法,争取早日拿到AC帽。
由数据范围反推算法复杂度以及算法内容
AcWing 3994. 水果派
C++
中除法是向下取整,如何向上取整?
$\left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor$
AcWing 3995. 最小的和
运用了多路归并
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1010;
int n, k1, k2;
int a[N], b[N], d[N];
int main()
{
cin >> n >> k1 >> k2;
int k = k1 + k2;
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = 0; i < n; i ++) cin >> b[i];
//因为结果是平方,范围是大于0的。正负没有影响。
for (int i = 0; i < n; i ++) d[i] = abs(a[i] - b[i]);
LL res = 0;
for (int i = 0; i < k; i ++ )
{
//每一次操作都找最大的
int t = 0;
for (int j = 0; j < n; j ++ )
if (d[j] > d[t])
t = j;
//最大值为0,那么我们判断还剩下多少操作次数,然后进行判断奇数就为1,偶数就为0。
if (!d[t])
{
res = (k - i) % 2;
break;
}
//由于是正是负,对最终结果没有影响。所以统一进行减1的操作。这样可以保证每个值都能接近零。
d[t] --;
}
for (int i = 0; i < n; i ++ ) res += (LL)d[i] * d[i];
cout << res << endl;
return 0;
}
第一道DP问题,纪念一下。⭐
AcWing 3996. 涂色
思想: 区间DP
因为本题涂色连通块只需要看成一次操作,我们可以把连通块都缩成一个点。
在本题解中,我们约定 $c_{i}$ 表示第 $i$ 个连通块的颜色,连通块总数为 $m$。
状态表示
$f_{i,j}$ 表示在区间 $[i,j]$ 中任选起点,最终使这一区间变成同一颜色的最少操作步数。(其中,$i,j$ 都是用于枚举连通块的下标)
状态转移
根据区间 DP 的常用转移顺序,我们考虑在外层循环枚举区间长度,内层循环枚举区间左端点 $i$(进而通过长度和左端点计算得到区间右端点 $j$)。由此可知,我们在考虑区间 $[i,j]$ 时,一定完成了对其所有子区间(不包括它本身)的状态计算。
本题代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
const int N = 5010;
int c[N], f[N][N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++){
cin >> c[i];
//将连通块看成一个点、
if (i && c[i] == c[i - 1]){
i --;
n --;
}
}
//因为长度为1的时候,不需要操作,不用枚举。
for (int len = 2; len <= n; len ++){
for (int l = 0; l + len - 1 < n; l ++){
int r = l + len - 1;
if (c[l] != c[r]) f[l][r] = min(f[l][r - 1], f[l + 1][r]) + 1;
else f[l][r] = f[l + 1][r - 1] + 1;
}
}
cout << f[0][n - 1] << endl;
return 0;
}
ac帽是什么?
功不唐捐,加油哦~
你也加油!😉