斜率优化

斜率优化=斜率优化DP。

共五道题,套路基本相同。

P3195 – 玩具装箱

题意

有 $n$ 个玩具,第 $i$ 个玩具价值为 $c_i$。要求将这 $n$ 个玩具排成一排,分成若干段。对于一段 $[l,r]$,它的代价为:

$$
(r-l+\sum_{i=l}^r c_i-L)^2
$$

求分段的最小代价。

$1\le n\le 5\times 10^4,1\le L,0\le c_i\le 10^7$.

DP

令 $f_i$ 表示前 $i$ 个物品,分若干段的最小代价。

状态转移方程:

$$
f_i=\min_{j<i}{\{f_j+(pre_i-pre_j+i-j-1-L)^2\}}
$$

其中 $pre_i$ 表示 $c$ 数列中,前 $i$ 个数的和,即 $\sum_{j=1}^i c_j$。

时间复杂度为 $O(n^2)$,无法解决本题。

优化

简化状态转移方程式:令 $s_i=pre_i+i,L’=L+1$,则

$$
f_i=\min_{j<i}{f_j+(s_i-s_j-L’)^2}
$$

我们目前优化的目的,是尽快地找到上面式子中的 $j$,也就是令 $f_i$ 最小化的继承状态。

为了表示方便,设 $j$ 为能使 $f_i$ 最小化的继承状态,所以有:

$$
f_i=f_j+(s_i-s_j-L’)^2
$$

考虑一次函数的斜截式 $y=kx+b$,将方程转化为这个形式。

其中变量 $x, y$ 与 $j$ 有关,$b, k$ 与 $j$ 无关,且要求 $x$ 随 $j$ 单调递增,$b$ 中包含 $f_i$(建模需要)。

按照上面的规则,对方程进行整理:

$$
\begin{aligned}
f_i&=f_j+[s_i-(s_j+L’)]^2\\
f_i&=f_j+{s_i}^2-2s_i(s_j+L’)+(s_j+L’)^2\\
f_i-{s_i}^2+2s_i(s_j+L’)&=f_j+(s_j+L’)^2\\
\end{aligned}
$$

也就是:

$$
f_j+(s_j+L’)^2=2s_i(s_j+L)+f_i-{s_i}^2
$$

与一次函数 $y=kx+b$ 对照地看,其中:

$$
\left\{
\begin{array}{lr}
y = f_j+(s_j+L’)^2\\
k = 2s_i\\
x = s_j+L\\
b = f_i-{s_i}^2
\end{array}
\right.
$$

我们把 $(x, y)$ 看成平面直角坐标系上的点。那么现在 $(x_j, y_j)$ 的意义就是:直线 $y=kx+b$ 上的一个点

又因为我们的目的是最小化 $f_i$,在上面的表示当中,$f_i$ 只与直线的截距 $b$ 有关。所以显然地,问题转化为:如何选取 $j$ ,才能使得过点 $(x_j, y_j)$ 的直线的截距 $b$ 最小。

注意到:直线的斜率不变。于是相当于平移直线 $y=kx$ ,直到其经过图中的一个点。

20190701195640154

如图,为了最小化 $b$,显然除了折线上面的点,都不可能是最优解。(这条折线上的点集就是凸包的一部分。

在折线上任取三个点 $A, B, C$ 满足 $x_A<x_b<x_c$,一定满足 $\operatorname{slope}(a,b)<\operatorname{slope}(b,=”” c)$.<=”” p=””> </x_b<x_c$,一定满足>

由图像又易知,最优解 $j$ 就是第一个 $\operatorname{slope}(j, j+1)>k$ 的点

于是可以得到 $\mathcal{O}(n\log n)$ 的算法。(处理凸包后,每次利用单调性二分)

由于随着 $i$ 的增长,$k=2s_i$ 也是单调递增的,不难发现可以用单调队列得到 $\mathcal{O}(n)$ 的算法。

设单调队列(递增)为 $q$,队首为 $head$,队尾为 $tail$,当前要转移 $i$ 号点,那么具体步骤:

  1. 当 $\operatorname{slope}(q_{head}, q_{head+1})\leq2 s_i$ 时,$head$++,(保证最优解)
  2. 此时的 $q_{head}$ 就是最优转移点,根据它和转移方程计算出 $f_i$,
  3. 当 $\operatorname{slope}(q_{tail-1}, q_{tail})\geq\operatorname{slope}(q_{tail}, i)$ 时,$tail$–,(维护下凸包
  4. 在队尾插入 $i$.

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e4 + 10;
int n, L;
int c[MAXN], s[MAXN], f[MAXN];
double slope(int i, int j) {
	return ((f[j]+(s[j]+L)*(s[j]+L)) - (f[i]+(s[i]+L)*(s[i]+L))) / (double)(s[j] - s[i]);
}
int head, tail, q[MAXN];
signed main() {
	scanf("%lld%lld", &n, &L);
	L += 1;
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &c[i]);
		s[i] = s[i - 1] + c[i] + 1;
	}
	head = tail = 1;
	for(int i = 1; i <= n; i++) {
		while(head < tail && slope(q[head], q[head + 1]) <= 2 * s[i]) {
            head++;
        }
		f[i] = f[q[head]] + (s[i] - s[q[head]] - L) * (s[i] - s[q[head]] - L);
		while(head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) {
            tail--;
        }
		q[++tail] = i;
	}
	printf("%lld", f[n]);
	return 0;
}

P3628 [APIO2010]特别行动队

题目描述

你有一支由 $n$ 名预备役士兵组成的部队,士兵从 $1$ 到 $n$ 编号,你要将他们拆分成若干特别行动队调入战场。出于默契的考虑,同一支特别行动队中队员的编号应该连续,即为形如 $(i, i + 1,\cdots, i+k)$ 的序列。所有的队员都应该属于且仅属于一支特别行动队。

编号为 $i$ 的士兵的初始战斗力为 $x_i$,一支特别行动队的初始战斗力 $X$ 为队内士兵初始战斗力之和,即 $x_i + x_{i+1} + \cdots + x_{i + k}$.

通过长期的观察,你总结出对于一支初始战斗力为 $X$ 的特别行动队,其修正战斗力 $X’=aX^2+bX+c$,其中 $a, b, c$ 是已知的系数 $a < 0$. 作为部队统帅,现在你要为这支部队进行编队,使得所有特别行动队的修正战斗力之和最大。

试求出这个最大和。

$1\leq n\leq 10^6, -5\leq a\leq -1, -10^7\leq b, c\leq 10^7, 1\leq x_i\leq 100$.

DP

与上一题类似。

令 $f_i$ 表示前 $i$ 个物品,分若干段的最小代价,有状态转移方程:

$$
f_i=\max_{j<i}{\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}}
$$

其中 $s_i$ 是 $x$ 数列的前缀和,也就是 $s_i=\sum_{j=1}^i{x_j}$.

优化

设 $j$ 是能使 $f_i$ 最大化的继承状态,那么整理状态转移方程:

$$
\begin{aligned}
f_i&=f_j+a(s_i-s_j)^2+b_(s_i-s_j)+c\\
f_i&=f_j+a({s_i}^2+{s_j}^2-2s_is_j)+b(s_i-s_j)+c\\
f_i&=f_j+a\cdot {s_i}^2+a\cdot {s_j}^2-2a\cdot s_is_j+b\cdot s_i-b\cdot s_j+c
\end{aligned}
$$

考虑一次函数斜截式 $y=kx+b$ 或 $b=y-kx$,将状态转移方程变换为这个形式。

其中变量 $x, y$ 与 $j$ 有关,$b, k$ 与 $j$ 无关

$$
\textcolor{red}{f_i-b\cdot s_i-a\cdot {s_i}^2}=\textcolor{purple}{(f_j+a\cdot {s_j}^2-b\cdot s_j+c)}-\textcolor{green}{2a\cdot s_i}\textcolor{blue}{s_j}
$$

所以:

$$
\left\{
\begin{array}{lr}
y = f_j+a\cdot {s_j}^2-b\cdot s_j+c\\
k = 2a\cdot s_i\\
x = s_j\\
b = f_i-b\cdot s_i-a\cdot {s_i}^2
\end{array}
\right.
$$

要最大化 $f_i$,也就是最大化截距 $b$,把 $(x_j, y_j)$ 看作平面直角坐标系上的点。

那么由于本题中 $k=2as_i$ ,是单调递减的,与上凸包单调性相同。所以与上一题类似,选取的点一定只在上凸包上,并且是第一个斜率小于 $k$ 的点

可以用单调队列维护:

设单调队列(递增)为 $q$,队首为 $head$,队尾为 $tail$,当前要转移 $i$ 号点,那么具体步骤:

  1. 当 $\operatorname{slope}(q_{head}, q_{head+1})\textcolor{red}{\geq}2a\cdot s_i$ 时,$head$++,(保证最优解)
  2. 此时的 $q_{head}$ 就是最优转移点,根据它和转移方程计算出 $f_i$,
  3. 当 $\operatorname{slope}(q_{tail-1}, q_{tail})\textcolor{red}{\leq}\operatorname{slope}(q_{tail}, i)$ 时,$tail$–,(维护上凸包
  4. 在队尾插入 $i$.

代码

#include <bits/stdc++.h>
#define int long long
#define x(X) (s[X])
#define y(X) (f[X] + a * s[X] * s[X] - b * s[X] + c)
using namespace std;
const int MAXN = 1e6 + 10;
int n;
int a, b, c;
int s[MAXN], f[MAXN];
int head, tail, q[MAXN];
double slope(int i, int j) {
	return 1.0 * (y(j) - y(i)) / (x(j) - x(i));
}
signed main() {
	scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
	for(int i = 1; i <= n; i++) {
		int tmp; scanf("%lld", &tmp);
		s[i] = s[i - 1] + tmp;
	}
	head = tail = 1;
	for(int i = 1; i <= n; i++) {
		while(head < tail && slope(q[head], q[head + 1]) >= 2ll * a * s[i]) {
            head++;
        }
		int j = q[head]; f[i] = f[j] + a * (s[i]-s[j])*(s[i]-s[j]) + b * (s[i]-s[j]) + c;
		while(head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i)) {
            tail--;
        }
		q[++tail] = i;
	}
	cout << f[n] << endl;
	return 0;
}

P3648 [APIO2014]序列分割

题目描述

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏,序列中第 $i$ 个元素的值为 $a_i$. 这个游戏中,你需要把序列分为 $k+1$ 个非空的块。为了得到 $k+1$ 块,你需要重复下面的操作 $k$ 次:

  • 选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
  • 选择两个相邻元素,把这个块从中间分开,得到两个非空的块。

每次操作后,你将获得那两个新产生的块的元素和的乘积的分数。

求总得分最大值,并输出任意一种分割方案

$2\leq n\leq 10^5, 1\leq k\leq \min{\{n-1, 200\}}$.

分析

首先可以发现,最终的分数与切的顺序无关

证明:对于长度为 $3$ 的序列 $xyz$,将其分为三部分,只有两种方法:

  1. 先分割 $xy$,再分割 $yz$,贡献为 $x(y+z)+yz=xy + yz + xz$,
  2. 先分割 $yz$,再分割 $xy$,贡献为 $(x+y)z + xy=xy+yz+xz$.

显然可以推广到更大的长度,于是结论得证。

DP

由于上面的结论,假设所有切割是按照从左到右的顺序进行的。

定义 $\operatorname{DP}_{i, j}$ 表示前 $i$ 个数,进行了 $j$ 次切割的最大得分,那么有状态转移方程:

$$
\operatorname{DP}_{i, k}=\max_{j<i}{\{\operatorname{DP}_{j, k-1}+s_j(s_i-s_j)\}}
$$

其中 $s$ 是题目序列中的元素前缀和,即 $s_i=\sum_{j=1}^{i}a_j$.

优化

考虑到斜率优化的形式,需要 $\operatorname{DP}$ 变成一维,又发现状态转移方程中,$\operatorname{DP}_i$ 只和 $\operatorname{DP}_{i-1}$ 有关,所以可以滚动数组

设 $f_i=\operatorname{DP}_{i, k}$,$g_j=\operatorname{DP}_{j, k-1}$,那么方程可以写为:

$$
f_i=\max_{j<i}{\{g_j+s_j(s_i-s_j)\}}
$$

这就很容易想到斜率优化。

设 $j$ 是能使 $f_i$ 最大化的继承状态,那么状态转移方程化为:

$$
f_i=g_j+s_j(s_i-s_j)
$$

考虑一次函数斜截式 $y=kx+b$,要把方程转化为这个形式。

其中变量 $x, y$ 与 $j$ 相关,常量 $b, k$ 与 $j$ 无关

于是:

$$
\begin{aligned}
f_i&=g_j+s_j(s_i-s_j)\\
f_i&=g_j+s_is_j-{s_j}^2\\
g_j-{s_j}^2&=-s_is_j+f_i
\end{aligned}
$$

所以:

$$
\left\{
\begin{array}{lr}
y = g_j-{s_j}^2\\
k = -s_i\\
x = s_j\\
b = f_i
\end{array}
\right.
$$

这里斜率 $k$ 是单调下降的,并且最优决策点 $(x_j, y_j)$ 是第一个满足 $\operatorname{slope}(j, j+1) < k$ 的点。所以最优决策点一定在上凸包上。

#include <bits/stdc++.h>
#define int long long
#define X(i) (s[i])
#define Y(i) (g[i] - s[i] * s[i])
using namespace std;
const long double inf = -1e18;
const int MAXN = 1e5 + 10;
int n, k;
int s[MAXN], f[MAXN], g[MAXN];
double slope(int i, int j) {
	if(s[j] == s[i]) return inf;
	return (Y(j) - Y(i)) / (double)(X(j) - X(i));
}
int head, tail, q[MAXN];
int to[210][MAXN];
signed main() {
	scanf("%lld%lld", &n, &k);
	for(int i = 1; i <= n; i++) {
		int tmp; scanf("%lld", &tmp);
		s[i] = s[i - 1] + tmp;
	}
	for(int l = 1; l <= k; l++) {
		head = tail = 1; q[1] = 0;
		for(int i = 1; i <= n; i++) {
			while(head < tail && slope(q[head], q[head + 1]) >= -1 * s[i]) {
                ++head;
            }
			int j = q[head]; to[l][i] = q[head];
			f[i] = g[j] + s[j] * (s[i] - s[j]);
			while(head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i)) { 
                tail--;
            }
			q[++tail] = i;
		}
		memcpy(g, f, sizeof(f));//把f复制到g
	}
	printf("%lld\n", f[n]);
	for(int i = k, j = n; i >= 1; i--) {
		j = to[i][j];
		printf("%lld ", j);
	}
	return 0;
}

P4360 [CEOI2004]锯木厂选址

题目描述

从山顶到山底下沿着一条直线种植了 $n$ 颗老树。当地的政府决定把它们砍下来。为了不浪费任何一颗木材,树被砍倒后要运送到锯木厂。

木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂,使得运输的费用总和最小。假定运输每公斤木材,移动每米需要一分钱。

题目给定第 $i$ 颗树的重量 $w_i$ ,以及第 $i$ 颗树与第 $i+1$ 颗树之间的距离 $d_i$.

请计算最小运输费用

$2\leq n\leq 20000, 1\leq w_i, d_i\leq 10000$,保证在 long long 范围内。

DP

https://blog.csdn.net/forever_dreams/article/details/97973474

这题难点可能在这部分…)

定义 $f_i$ 为以 $i$ 作为第二个锯木厂的最小花费,$s_i$ 为 $w_i$ 的前缀和,$dis_i$ 为 $d_i$ 的后缀和,$cost$ 为 $w_i\times dis_i$ 的总和。

转移就是通过枚举第一个锯木厂,然后减去省掉的花费。有下面的转移方程:

$$
f_i=\min_{j<i}{\{cost – s_j\times dis_j-(s_i-s_j)\times dis_i\}}
$$

斜率优化

这部分和前面都一样,所以字越来越少……

设 $j$ 最优,化简:

$$
\begin{aligned}
f_i&=cost-s_j\times dis_j-s_i\times dis_i+s_j\times dis_i\\
s_j\times dis_j&=s_j\times dis_i+(cost-f_i-s_i\times dis_i)
\end{aligned}
$$

所以:

$$
\left\{
\begin{array}{lr}
y = s_j\times dis_j\\
k = dis_i\\
x = s_j\\
b = cost-f_i-s_i\times dis_i
\end{array}
\right.
$$

$k=dis_i$ 是后缀和,单调递减。又因为要最小化 $f_i$,所以要最大化 $b$。

所以最优决策点 $(x_j, y_j)$ 是第一个满足 $\operatorname{slope}(j, j+1)<k$ 的点,单调队列维护上凸包即可。<=”” p=””> </k$>

代码

#include <bits/stdc++.h>
#define int long long
#define X(i) (s[i])
#define Y(i) (s[i] * dis[i])
using namespace std;
const int MAXN = 2e4 + 10;
int n;
int w[MAXN], d[MAXN];
int cost, s[MAXN], dis[MAXN], f[MAXN];
double slope(int i, int j) {
	return (Y(j) - Y(i)) / (double)(X(j) - X(i));
}
int head, tail, q[MAXN];
int ans = 1e18;
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) scanf("%lld%lld", &w[i], &d[i]);
	for(int i = 1; i <= n; i++) s[i] = s[i - 1] + w[i];
	for(int i = n; i >= 1; i--) dis[i] = dis[i + 1] + d[i];
	for(int i = 1; i <= n; i++) cost += w[i] * dis[i];
	head = tail = 1;
	for(int i = 1; i <= n; i++) {
		while(head < tail && slope(q[head], q[head + 1]) >= dis[i]) ++head;
		int j = q[head];
		f[i] = cost - s[j] * dis[j] - (s[i] - s[j]) * dis[i];
		ans = min(ans, f[i]);
		while(head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i)) tail--;
		q[++tail] = i;
	}
	printf("%lld\n", ans);
	return 0;
}

P2900 [USACO08MAR]Land Acquisition G

题目描述

翻译的不是很好,所以我简化一下题面。

给定 $n$ 个矩阵的宽 $w$ 和高 $h$,每次选一个矩阵集合,代价为集合中的 $\max{\{w\}}\times \max{\{h\}}$。

任意两次之间没有重复的矩阵,求取完所有矩阵的最小代价

分析

注意到对于两个矩阵 $i, j$,如果 $w_i\leq w_j$ 并且 $h_i\leq h_j$,那么 $i$ 和 $j$ 一定可以放到一组,$i$ 对答案没有贡献,不用考虑,可以直接删去。

比如下图当中的 $1$ 和 $2$. 矩阵 $2$ 能完全被 $1$ 包含,所以 $2$ 没有贡献,可以删去。

P2900-1

于是考虑先删除所有 $i$ 这样的矩阵。

具体做法就是:按照 $h$ 为第一关键字,$w$ 为第二关键字从大到小排序,之后双指针扫一遍即可。

//a已经降序排序
int t = 0;
for(int i = 1; i <= n; i++) {
	if(a[i].w > a[t].w) a[++t] = a[i];
}

如上图,剩下的只有 $1, 3$ 号矩阵。

删完之后剩下的就是一个,$h$ 严格单调递减,$w$ 严格单调递增的序列。考虑 $DP$ 解决。

DP

设 $f_i$ 为新序列中,取走前 $i$ 个矩阵的最小花费,$w$ 为宽(单调递增),$h$ 为高(单调递减),那么有转移方程:

$$
f_i=\min_{j=0}^{i}{\{f_{j}+w_ih_{j+1}\}}
$$

相当于,把 $j+1$ 到 $i$ 这一段合为一组取走。由于单调性,所以这一组的 $\max{\{w\}}=w_i$,$\max{\{h\}}=h_{j+1}$.

复杂度 $\mathcal{O}(n^2)$。这显然可以斜率优化。

斜率优化

我们目前优化的目的,是尽快地找到 $f_i$ 到底是由哪个 $j$ 转移过来的,也就是尽快找到最小化 $f_i$ 的继承状态。

为了表示方便,设 $j$ 为能使 $f_i$ 最小化的继承状态,所以有:

$$
f_i=f_{j}+w_ih_{j+1}
$$

考虑一次函数斜截式 $y=kx+b$ 或 $b=y-kx$,将状态转移方程变换为这个形式:

$$
f_{j}=-w_ih_{j+1}+f_i
$$

其中变量 $x, y$ 与 $j$ 有关,$b, k$ 与 $j$ 无关。且要求 $x$ 随 $j$ 单调递增,$b$ 中包含 $f_i$(斜率优化基本操作)。

所以可以构造出直线方程为:

$$
\left\{
\begin{array}{lr}
y = f_j\\
k = w_i\\
x = -h_{j+1}\\
b = f_i
\end{array}
\right.
$$

$x$ 随 $j$ 单调递增,$k$ 随 $i$ 单调递增,要使截距 $b=f_i$ 最小,最优解 $j$ 就是从左往右枚举到的第一个 $\operatorname{slope}(j, j+1)>k$ 的点

所以单调队列维护下凸包即可。

代码

#include <bits/stdc++.h>
#define X(i) (-a[i+1].h)
#define Y(i) (f[i])
#define int long long
using namespace std;
const int MAXN = 5e4 + 10;
int n;
struct Node{
	int w, h;
} a[MAXN];
int f[MAXN];
bool cmp(Node i, Node j) {
	return (i.h > j.h) || (i.h == j.h && i.w > j.w);
}
double slope(int i, int j) {
	return (Y(j) - Y(i)) / (double)(X(j) - X(i));
}
int head, tail, q[MAXN];
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld%lld", &a[i].w, &a[i].h);
	}
	sort(a + 1, a + n + 1, cmp);
	int t = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i].w > a[t].w) a[++t] = a[i];
	}
	n = t;
	head = tail = 1;
	for(int i = 1; i <= n; i++) {
		while(head < tail && slope(q[head], q[head + 1]) <= a[i].w) {
			head++;
		}
		int j = q[head]; f[i] = f[j] + a[i].w * a[j + 1].h;
		while(head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) {
			tail--;
		}
		q[++tail] = i;
	}
	cout << f[n] << endl;
	return 0;
}

总结?

如果转移方程能表示成:$f_i=\max_{j<i}{\{a_ib_j+c_j+d_i\}}$ 的形式(或=”” $\min$),并且=”” $a_i$=”” 关于=”” $i$=”” 有单调性,就都可以用斜率优化。<=”” p=””> </i}{\{a_ib_j+c_j+d_i\}}$>

斜率优化能把 $\mathcal{O}(n^2)$ 降成 $\mathcal{O}(n)$.

数形结合。

代码短。

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇