第三周
1. 最短时间
第一种思路
求矩阵到目标点的最短曼哈顿距离,注意下标从一开始。
代码如下
int a = max(n - r, r - 1);
int b = max(m - c, c - 1);
printf("%d\n", a + b);
2. 重置数列
第一种思路
因为 $1 <= a[i] <= 100$, 所以枚举将序列值赋值为 $[1~100]$ 时用的操作数最小是多少,就可以了。
同时,因为一次选中的数必须是连续的,所以由贪心的思想可知,每当找到一个需要修改的数,就跳过之后 $k - 1$ 个数继续找,并增加一次操作次数。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int T;
int n, k;
int a[N];
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
int ans = INF, cnt;
for (int i = 1; i <= 100; i ++ )
{
cnt = 0;
for (int j = 1; j <= n; j ++ )
{
if (a[j] != i)
{
j += (k - 1);
cnt ++;
}
}
ans = min(ans, cnt);
}
printf("%d\n", ans);
}
return 0;
}
3. 最大上升子序列和
第一种思路
实际代码中直接用线段树更新,没有用到dp数组
$dp[x]$表示以 $x$ 为结尾的序列的最大和
很容易想到
$dp[x]=max{dp[1],dp[2],dp[3]....dp[x-1]} + x$
$max{dp[1],dp[2],dp[3]....dp[x-1]}$ 是一段连续元素的最大值,显然可以用线段树来维护.
但是这道题目的 $a[i]$ 太大了,不能直接建立线段树维护,所以我们进行离散化处理
现在,我们令 $dp[x]$ 表示以第 $x$ 大的数结尾的序列最大和
$dp[x]=max{dp[1],dp[2],dp[3]....dp[x-1]} +$ 第 $x$ 大的数
$max{dp[1],dp[2],dp[3]....dp[x-1]}$ 当然也可以用线段树来维护.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int N = 1e5+10;
ll a[N];
int pos[N];
vector<ll> v;
int find(ll x){
int l = 1, r = v.size() - 1;
while (l < r)
{
ll mid = l + r >> 1;
if (v[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
struct Node
{
int l, r;
// TODO: 需要维护的信息和懒标记
ll dat;
}tr[N * 4];
void pushup(int u)
{
// TODO: 利用左右儿子信息维护当前节点的信息
tr[u].dat = max(tr[u << 1].dat, tr[u << 1 | 1].dat);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, 0};
else
{
tr[u] = {l, r, 0};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void update(int u, int l, int r, ll d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
// TODO: 修改区间
tr[u].dat = d;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) update(u << 1, l, r, d);
if (r > mid) update(u << 1 | 1, l, r, d);
pushup(u);
}
}
ll query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].dat; // TODO 需要补充返回值
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
ll res = 0;
if (l <= mid ) res = query(u << 1, l, r);
if (r > mid) res = max(query(u << 1 | 1, l, r), res);
return res;
}
}
int main ()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ){
scanf("%lld", &a[i]);
v.push_back(a[i]);
}
v.push_back(0);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for (int i = 1; i <= n; i ++ )
{
pos[i] = find(a[i]);
}
build(1, 1, n);
for (int i = 1; i <= n; i ++ ){
ll p = pos[i];
if (p == 1)
{
update(1, p, p, a[i]);
continue;
}
ll pmax = query(1, 1, p-1);
update(1, p, p, pmax + a[i]);
}
ll ans = query(1, 1, n);
printf("%lld", ans);
return 0;
}