今天在讲讲座，讲斜率优化、四边形不等式优化、凸包，还有一大堆东西。
因为就觉得自己目前最重要的不是这些，就回机房做题了，（GD 的省一应该用不到这些 QAQ）
[HAOI2009] 逆序对数列
做了一下以前高中部上课题和作业题，把以前有一道题的笔记订正了，原来是错的，因为数据范围不一样。
这道题还带一个前缀和优化。可以发现，朴素的做法是 $O(nk^2)$ 的，在这道题的数据会超时。然后又会发现，第 3 层循环的作用就是把 $f[i][...]$ 加起来，所以说可以想到前缀和的做法。详情见题解。
还有，记得要取模！
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e3+5;
const int Mod = 1e4;
int n, k, f[MAXN][MAXN];
int main() {
scanf ("%d%d",&n,&k);
f[1][0]=1;
for (int i=2; i<=n; i++) {
int sum = 0;
for (int j=0; j<=k; j++) {
sum += f[i-1][j];
sum %= Mod;
f[i][j]=sum;
if ( j-i+1 >= 0 ) {
sum = ( sum-f[i-1][j-i+1]+Mod )%Mod;
}
}
}
printf ("%d\n",f[n][k]);
return 0;
}[HNOI] 消防局的设立
洛谷下不了数据，还是 $LOJ$ 好 qwq
这道题有两种做法，我自己第一次想觉得是贪心 + $dfs$ 。不过这道题在试炼场中被归为“动态规划”，然鹅我菜的并不知道怎么在“图”中进行 $dp$ 。题解第一篇就是贪心，才 21 行，但是我还是忍住去写 $dp$ 了。
其实这种 ”图“ 中 $dp$ ，就是树形 $dp$ ，之前没有打过。就看了题解 qwq
设计状态：$f[i][j]$，其中 $i$ 表示当前节点，$j$ 的范围是 0~4，分别表示：
$f[i][0]$：当前点作为消防站，需要的最小站点数
$f[i][1]$：儿子节点作为消防站，需要的最小站点数
$f[i][2]$：孙子节点作为消防站，需要的最小站点数
$f[i][3]$：儿子节点被覆盖，需要的最小站点数
$f[i][4]$：孙子节点被覆盖，需要的最小站点数
至于转移方程，我懒得写了，放个题解链接在这里当做标记。
$Code$
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1005;
const int INF = 2e9;
struct Node {
int next, v;
}edge[MAXN];
int f[MAXN][5], n, cnt, head[MAXN];
inline void AddEdge (int u, int v) {
cnt++;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
return;
}
void dfs (int x) {
f[x][0]=1;
f[x][3]=0;
f[x][4]=0;
for (int i=head[x]; i!=0; i=edge[i].next) {
int v=edge[i].v;
dfs (v);
f[x][0]+=f[v][4];
f[x][3]+=f[v][2];
f[x][4]+=f[v][3];
}
if (head[x] >= 0) {
f[x][1]=INF;
f[x][2]=INF;
for (int i=head[x]; i!=0; i=edge[i].next) {
int v=edge[i].v;
int a=f[v][0];
int b=f[v][1];
for (int j=head[x]; j!=0; j=edge[j].next) {
if (i == j) continue;
int k=edge[j].v;
a += f[k][3];
b += f[k][2];
}
f[x][1]=min(a,f[x][1]);
f[x][2]=min(b,f[x][2]);
}
} else {
f[x][1]=f[x][2]=1;
}
for (int i=1; i<=4; i++) {
f[x][i]=min(f[x][i], f[x][i-1]);
}
return;
}
int main() {
scanf ("%d",&n);
for (int i=2; i<=n; i++) {
int t;
scanf ("%d",&t);
AddEdge (t,i);
}
dfs(1);
printf ("%d\n",f[1][2]);
return 0;
}这只是第一种做法，还有贪心的做法，说学会了基本上就能解决形如半径为 $k$ 的最小覆盖问题，复杂度仅为 $O(nk)$ 。
如果 1 为根节点，那么可以考虑最深节点的覆盖问题，如果它要被覆盖，有 3 种情况：
- 爷爷
- 父亲
- 兄弟
为了让这个消防站最不浪费，肯定把站点设在爷爷节点，如此刷新最深未被覆盖的节点，把站点设在他的爷爷节点，这样的贪心策略一定最优。
当然还有一些优化（对于这道题不加这些优化也可以过），深度可以在读入的时候处理，对于判断是否被覆盖的问题，用一个数组 MinDis[i] 储存距离 $i$ 最近的消防站离 $i$ 的距离，如果这个距离大于 2 的话，就要加个消防站，每次从父节点和爷爷节点更新。
$Code$
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e3+5;
int MinDis[MAXN], n, num[MAXN], fa[MAXN], dis[MAXN], ans;
bool cmp (int a, int b) {
return dis[a]>dis[b];
}
int main() {
memset (MinDis, 0x7f, sizeof (MinDis));
scanf ("%d",&n);
num[1]=1;
for (int i=2; i<=n; i++) {
scanf ("%d",&fa[i]);
dis[i]=dis[fa[i]]+1;
num[i]=i;
}
sort (num+1, num+n+1, cmp);
for (int i=1;i<=n;i++) {
int j=num[i];
int f=fa[j], pa=fa[fa[j]];
MinDis[j]=min (MinDis[j], min(MinDis[f]+1, MinDis[pa]+2));
if (MinDis[j] > 2) {
MinDis[pa]=0;
ans++;
MinDis[fa[pa]]=min (1, MinDis[fa[pa]]);
MinDis[fa[fa[pa]]]=min (2, MinDis[fa[fa[pa]]]);
}
}
printf ("%d\n",ans);
return 0;
}本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/71/
最后修改时间：2020-04-13 11:35:29
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！