这周事情比较多，Hard可能会鸽点
630. 课程表III
简单点说，本题就是变种题
原模型大概是：给一定量的课程及其起止时间，时间安排好的情况下，最多可以上多少节课。
这种问题就是典型的求不相交的情况下的最多可以获得的线段数量。
那么本题在原模型的基础上，将起止时间改成了不限开始时间，但是给定了上完课程的最迟时间。
那么我们就可以不停地堆这些课程，同样的，也是需要尽可能保留结束时间越早的课程，这样可以使得更多的课程能被学习。
同样的贪心操作，优先选择截止时间早的课程，尽可能保证这些课程可以被学习到。
但是有一个不同的地方时，我们可以控制我们的结束时间。
如果说存在一门课程A，比另一门课程B结束的早，且不耽误其他课程，那么我们可以选择A，放弃B。
因为B使用了更多的时间，导致我们的结束时间晚了，而且并没有使得我们学习到更多的课程。
class Solution {
public:
int scheduleCourse(vector>& courses) {
sort(courses.begin(), courses.end(), [](vector &A, vector &B) {return A[1] < B[1];});
priority_queue q;
int now = 0;
for(int i = 0; i < courses.size(); ++i) {
int t = courses[i][0];
int d = courses[i][1];
if(now + t <= d) now += t, q.push(t);
else {
if(!q.empty() && t < q.top()) {
now += t - q.top();
q.pop();
q.push(t);
}
}
}
return (int)q.size();
}
};
LCP05. 发LeetCoin
本意是模拟lazytag，注意到数据范围是50000后就明白做法错了
但还是发下吧，这样的复杂度是可以退化到
O
(
n
2
)
O(n^2)
O(n2)的，关系为一条
1
→
2
→
3
→
.
.
.
→
n
1→2→3→...→n
1→2→3→...→n的链即可。
class Solution {
public:
vector> g;
vector boss;
vector coin;
vector flag;
const int mod = 1e9 + 7;
void add(int& a, int b) {
a = a + b;
if(a >= mod) a -= mod;
}
int getAll(int u) {
int sum = coin[u];
for(auto v : g[u]) {
for(auto c : g[v]) {
add(coin[c], flag[v]);
add(flag[c], flag[v]);
}
flag[v] = 0;
sum += getAll(v);
}
return sum;
}
int query(int u) {
vector seq;
int temp = u;
while(temp != -1) seq.push_back(temp), temp = boss[temp];
reverse(seq.begin(), seq.end());
for(auto u : seq) {
for(auto v : g[u]) {
add(coin[v], flag[u]);
add(flag[v], flag[u]);
}
flag[u] = 0;
}
return getAll(u);
}
vector bonus(int n, vector>& leadership, vector>& operations) {
g = vector>(n + 1);
boss = vector(n + 1, -1);
for(auto u : leadership) {
g[u[0]].push_back(u[1]);
boss[u[1]] = u[0];
}
vector res;
coin = vector(n + 1, 0);
flag = vector(n + 1, 0);
for(auto u : operations) {
if(u[0] == 1) add(coin[u[1]], u[2]);
else if(u[0] == 2) add(coin[u[1]], u[2]), add(flag[u[1]], u[2]);
else res.push_back(query(u[1]));
}
return res;
}
};
正解应该是利用dfs序编号，然后树状数组 or 线段树维护区间和即可
class Solution {
public:
vector> g;
vector st, ed;
int tim;
int n;
struct Node {
int l, r;
int sum;
int flag;
}tr[50010 * 4];
const int mod = 1e9 + 7;
void add(int& a, int b) {
a = a + b;
if(a < 0) a += mod;
if(a >= mod) a -= mod;
}
void dfs(int u) {
st[u] = ++tim;
for(auto& v : g[u]) dfs(v);
ed[u] = tim;
}
void pushup(int u) {
int sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
if(sum >= mod) sum -= mod;
tr[u].sum = sum;
}
void pushdown(int u) {
if(tr[u].flag) {
add(tr[u << 1].sum, 1ll * tr[u].flag * (tr[u << 1].r - tr[u << 1].l + 1) % mod);
add(tr[u << 1].flag, tr[u].flag);
add(tr[u << 1 | 1].sum, 1ll * tr[u].flag * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) % mod);
add(tr[u << 1 | 1].flag, tr[u].flag);
tr[u].flag = 0;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int x) {
if(tr[u].l >= l && tr[u].r <= r) {
add(tr[u].sum, 1ll * (tr[u].r - tr[u].l + 1) * x % mod);
add(tr[u].flag, x);
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, x);
if(r > mid) modify(u << 1 | 1, l, r, x);
pushup(u);
}
int query(int u, int l, int r) {
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int sum = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) add(sum, query(u << 1, l, r));
if(r > mid) add(sum, query(u << 1 | 1, l, r));
return sum;
}
vector bonus(int _n, vector>& leadership, vector>& operations) {
tim = 0;
n = _n;
st = vector(n + 1, -1);
ed = vector(n + 1, -1);
g = vector>(n + 1);
for(auto u : leadership) g[u[0]].push_back(u[1]);
dfs(1);
build(1, 1, n);
vector res;
for(auto u : operations) {
if(u[0] == 1) modify(1, st[u[1]], st[u[1]], u[2]);
else if(u[0] == 2) modify(1, st[u[1]], ed[u[1]], u[2]);
else res.push_back(query(1, st[u[1]], ed[u[1]]));
}
return res;
}
};
1278. 分割回文串III
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示前
i
i
i个字符分割成
j
j
j个回文串需要修改的最小字符数
c
o
s
t
[
i
]
[
j
]
cost[i][j]
cost[i][j]表示从将
s
.
s
u
b
s
t
r
(
i
,
j
−
i
+
1
)
s.substr(i,j-i+1)
s.substr(i,j−i+1)修改成回文串需要修改的最小字符数，
O
(
n
2
)
O(n^2)
O(n2)预处理
f
[
i
]
[
j
]
=
m
i
n
(
{
f
[
i
−
o
]
[
j
−
1
]
+
c
o
s
t
(
i
−
o
,
i
−
1
)
}
)
,
o
∈
[
1
,
i
−
(
j
−
1
)
]
f[i][j]=min({f[i-o][j-1]+cost(i-o,i-1)}), oin[1,i-(j-1)]
f[i][j]=min({f[i−o][j−1]+cost(i−o,i−1)}),o∈[1,i−(j−1)]
时间复杂度：
O
(
n
2
k
)
+
O
(
n
2
)
=
O
(
n
2
k
)
O(n^2k) + O(n^2) =O(n^2k)
O(n2k)+O(n2)=O(n2k)
class Solution {
public:
int palindromePartition(string s, int k) {
const int INF = 0x3f3f3f3f;
int n = s.size();
vector> cost(n, vector(n, 0));
for(int i = 2; i <= n; ++i)
for(int l = 0, r; l + i - 1 < n; ++l) {
r = l + i - 1;
cost[l][r] = INF;
cost[l][r] = min(cost[l][r], cost[l + 1][r - 1] + (s[l] == s[r] ? 0 : 1));
}
vector> f(n + 1, vector(k + 1, INF));
f[0][0] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= min(k, i); ++j)
for(int o = 1; i - o >= j - 1; ++o)
f[i][j] = min(f[i][j], f[i - o][j - 1] + cost[i - o][i - 1]);
return f[n][k];
}
};
