浅谈状压 DP
Californium_qwq
·
2026-11-14 16:11:16
·
算法·理论
前言(废话)
本人为区一 ,写的有问题还望多多包涵。
正题
常用位运算
(S >> i) & 1:检查第 i 位是否为 1 。
S | (1 << i):将第 i 位设为 1 。
S & (~(1 << i)):将第 i 位变为 0 。
S & (-S):获取最低位的 1 的位置。
S & (S - 1):将最低位的 1 变为 0 (用于枚举子集)。
S ^ (1 << i):将 S 的第 i 位取反。
for (int T = S; T; T = (T - 1) & S):枚举 S 的所有子集,总复杂度 O(|S|^3) 。
例题
普通状压
发现 n\le 20 考虑状压或搜索。
普通状压 DP 通常用来维护集合中存在 哪些元素。
由于 n 很小,通常可以有较高复杂度的预处理。
状压 DP 常熟极小,所以这 2 种可以过。
首先本质不同的罚款只有 n^2 种。
发现可以从大到小插入,假入在第 i 位插入,[l,i) 和 (i,r] 都没被插入,则只有左端点在 [l,i] ,右端点在 [i,r] 的区间贡献和 i 有关。
然后插入时可以向左右扩展找到 l 和 r ,如果同时统计贡献的话复杂度较高,O(n^5) 预处理插入的贡献即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e1 + 10;
const int M = (1 << 20);
int n, k, m, cr[N], a[N][N], b[N][N][N], dp[M];
// b[i][l][r]:在 i 插入,[l,i) 和 (i,r] 没被插入的贡献
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k >> m;
for(int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
a[l][r]++;
}
for(int i = 1; i <= n; i++) {
cr[i] = k - i + 1;
if(i > k) cr[i] = 0;
}
for(int i = 1; i <= n; i++)
for(int l = 1; l <= i; l++)
for(int r = i; r <= n; r++)
for(int ll = l; ll <= i; ll++)
for(int rr = i; rr <= r; rr++)
b[i][l][r] += a[ll][rr];
memset(dp, 0x3f, sizeof dp), dp[0] = 0;
for(int S = 1; S < (1 << n); S++) {
int cnt = 0, ss = S;
while(ss) cnt += (ss & 1), ss >>= 1;
for(int i = 1; i <= n; i++) {
if(!(S & (1 << i - 1))) continue;
int T = S ^ (1 << i - 1), l = i, r = i;
while(l > 1 && !(S & (1 << l - 2))) l--;
while(r < n && !(S & (1 << r - 0))) r++;
dp[S] = min(dp[S], dp[T] + b[i][l][r] * cr[cnt]);
}
} cout << dp[(1 << n) - 1];
}
P7296 [USACO21JAN] Uddered but not Herd G
思路和上一题有异曲同工之处。
设 dp_S 表示将 S 插入到字母表的前 |S| 位的最小轮数。
考虑转移,将 i 插入到字母表的 |S| + 1 位,我们发现若一个 S 中的元素出现在 i 的左边,此时又唱了一轮字母表。
然后预处理相邻字母为 s_1 和 s_2 的数量 sum_{s_1,s_2} ,O(2^nn^2) DP 即可。
这题因为不包含 Mildred 中的字母,只有 20 种字符,需要离散化。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int M = (1 << 20);
int n, cnt, lsh[N], a[N];
int dp[M], sum[30][30];
string s;
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> s;
n = s.size();
s = ' ' + s;
for(int i = 1; i <= n; i++) lsh[i] = s[i];
sort(lsh + 1, lsh + 1 + n);
cnt = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
for(int i = 1; i <= n; i++) a[i] = lower_bound(lsh + 1, lsh + 1 + cnt, s[i]) - lsh - 1;
for(int i = 2; i <= n; i++) sum[a[i - 1]][a[i]]++;
memset(dp, 0x3f, sizeof dp), dp[0] = 1;
for(int S = 0; S < (1 << cnt); S++) {
for(int i = 0; i < cnt; i++) {
if((S & (1 << i))) continue;
int T = S | (1 << i), val = dp[S];
for(int j = 0; j < cnt; j++) {
if((T & (1 << j))) {
val += sum[i][j];
}
} dp[T] = min(dp[T], val);
}
} cout << dp[(1 << cnt) - 1];
}
P7296 [USACO21JAN] Uddered but not Herd G
发现可以用 \text{Floyd} 得到最短路,再得到每个点再那些受灾区的最短路上。
然后发现这可以 DP,设 dp_S 表示 S 的受灾区最短路有补给点的最小代价。
暴力转移是 O(2^k\times n) 的,但是状压常熟极小,能过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e2 + 10;
const int M = (1 << 20);
int n, m, b, f[N], c[N];
int dis[N][N], sta[N], dp[M];
void Floyd() {
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
for(int j = 1; j <= n; j++) {
for(int i = 1; i <= m; i++) {
if(dis[1][c[i]] == dis[1][j] + dis[j][c[i]])
sta[j] |= (1 << i - 1);
}
}
}
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> b >> m;
memset(dp, 0x3f, sizeof dp);
memset(dis, 0x3f, sizeof dis);
for(int i = 1; i <= n; i++) cin >> f[i];
for(int i = 1; i <= m; i++) cin >> c[i];
for(int i = 1; i <= n; i++) dis[i][i] = 0;
for(int i = 1, u, v, w; i <= b; i++) {
cin >> u >> v >> w;
dis[u][v] = min(dis[u][v], w);
dis[v][u] = min(dis[v][u], w);
} Floyd(), dp[0] = 0;
for(int S = 0; S < (1 << m); S++) {
for(int i = 1; i <= n; i++) {
if(!f[i]) continue;
int T = S | sta[i];
dp[T] = min(dp[T], dp[S] + 1);
}
} cout << dp[(1 << m) - 1];
}
P5911 [POI 2004] PRZ
直接设 dp_S 表示过桥状态为 S 的最小代价。
然后可以预处理不同集合的人一次性过桥的重量和时间。
枚举子集暴力转移即可,枚举子集复杂度总和是 O(3^n) ,能通过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e1 + 10;
const int M = (1 << 20);
int n, m, a[N], b[N], t[M], w[M], dp[M];
void getmin(int &x, int y) {x = min(x, y);}
void getmax(int &x, int y) {x = max(x, y);}
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> m >> n;
memset(dp, 0x3f, sizeof dp);
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
for(int S = 1; S < (1 << n); S++) {
for(int i = 1; i <= n; i++) {
if(!(S & (1 << i - 1))) continue;
getmax(t[S], a[i]), w[S] += b[i];
}
} dp[0] = 0;
for(int S = 1; S < (1 << n); S++) {
for(int T = S; T; T = (S & T - 1)) {
if(w[T] <= m) getmin(dp[S], dp[S ^ T] + t[T]);
if(T == 0) break;
}
} cout << dp[(1 << n) - 1];
}
P2704 [NOI2001] 炮兵阵地
对于这种棋盘上状压 的经典题还是讲一下吧。
打一下表发现,在判断当前行是否合法后,每一行的状态只有 $O(n)$ 种。
直接设 $dp_{i,S,T}$ 表示考虑前 $i$行,第 $i$ 行为 $S$,第 $i - 1$ 行为 $T$。
枚举下一行转移,复杂度约为 $O(n^4)$。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e2 + 10;
const int M = (1 << 10);
int n, m, sta[N], cnt[M];
int id[M], dp[N][N][N];
vector<int> v;
void getmax(int &x, int y) {x = max(x, y);}
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
char ch; cin >> ch;
if(ch == 'P') continue;
sta[i] |= (1 << j - 1);
}
for(int S = 0; S < (1 << m); S++) {
cnt[S] = __builtin_popcountll(S);
int check = ((S << 2) | (S << 1) | (S >> 1) | (S >> 2));
if(!(check & S)) v.push_back(S), id[S] = v.size();
} memset(dp, -1, sizeof dp); dp[0][1][1] = 0;
for(int i = 1; i <= n; i++) {
for(int S : v) {
if((S & sta[i])) continue;
for(int T : v) {
if((T & sta[i - 1])) continue;
for(int A : v) {
if(i > 1 && (A & sta[i - 2])) continue;
if((S & T) | (S & A) | (T & A)) continue;
if(dp[i - 1][id[T]][id[A]] < 0) continue;
getmax(dp[i][id[S]][id[T]], dp[i - 1][id[T]][id[A]] + cnt[S]);
}
}
}
} int ans = 0;
for(int S : v)
for(int T : v)
getmax(ans, dp[n][id[S]][id[T]]);
cout << ans;
}
```
#### [P7519 [省选联考 2021 A/B 卷] 滚榜](https://www.luogu.com.cn/problem/P7519)
设 $dp_{S,i,j,k}$ 表示考虑前 $i$ 个,前 $|S|$ 名为 $S$ 内元素,第 $|S|$ 名为 $i$,总过题数为 $j$,前一个过题数为 $k$。
发现枚举过题数太慢了 $O(m^2)$,发现可以贪心,每次尽量少选。
把 $b$ 差分一下,然后每次最小化当前的 $b$,因为是差分数组,所以会对后面带来贡献,额外计算对后面的贡献即可。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e1 + 4;
const int M = 5e2 + 10;
int n, m, a[N], ma = 1;
int dp[1 << N][N][M]; // [点集][当前位置][最小b总和]
int lowbit(int x) {return x & -x;}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m; int kk = (1 << n) - 1;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) if(a[i] > a[ma]) ma = i;
for(int i = 1; i <= n; i++) {
int sum = n * (a[ma] - a[i]);
if(ma < i) sum += n;
if(sum > m) continue;
dp[1 << i - 1][i][sum] = 1;
}
for(int S = 1; S <= kk; S++) {
int cnt = n, S_ = S;
while(S_) cnt -= S_ & 1, S_ >>= 1;
for(int T = S; T; T -= lowbit(T)) {
int j = __lg(lowbit(T)) + 1;
for(int E = kk - S; E; E -= lowbit(E)) { // 用 lowbit 优化枚举元素
int i = __lg(lowbit(E)) + 1;
for(int b = 0; b <= m; b++) {
int sum = cnt * (a[j] - a[i]);
if(j < i) sum += cnt;
sum = max(sum, 0ll) + b;
if(sum > m) continue;
dp[S | (1 << i - 1)][i][sum] += dp[S][j][b];
}
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++) // 这里最小化了费用,所以 < m 也是合法的
ans += dp[kk][i][j];
cout << ans;
}
```
#### [P3959 [NOIP 2017 提高组] 宝藏](https://www.luogu.com.cn/problem/P3959)
首先答案的图一定是个树。
考虑暴力枚举根节点(赞助的点),然后对树进行扩展。
发现扩展时的代价与新点的深度和边的长度有关,于是对其进行 DP。
设 $dp_{i,S}$ 表示考虑深度 $\le i$ 的点,已经选的点集为 $S$,最小的代价。
发现转移不方便,设辅助数组 $deta_{S,T}$ 表示将 $S$ 的点连边后变成 $T$ 的最小代价,然后就好转移了。
这里面会有错的转移,但它更不优,所以不用管。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e1 + 3;
const int M = (1 << 12);
const int INF = 0x3f3f3f3f;
int n, m, w[N][N], deta[M][M], dp[N][M];
void getmin(int &x, int y) {x = min(x, y);}
int DP(int x) {
memset(dp, 0x3f, sizeof dp);
dp[0][1 << x - 1] = 0;
for(int i = 1; i < n; i++) {
for(int S = 1; S < (1 << n); S++) {
for(int T = S; T; T = (T - 1) & S) {
if(S == T) continue;
getmin(dp[i][S], dp[i - 1][T] + deta[T][S] * i);
}
}
} int res = INF;
for(int i = 1; i < n; i++)
getmin(res, dp[i][(1 << n) - 1]);
return res;
}
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(w, 0x3f, sizeof w);
memset(dp, 0x3f, sizeof dp);
for(int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
getmin(w[u][v], c);
getmin(w[v][u], c);
}
if(n == 1) {cout << 0; return 0;}
for(int S = 1; S <= (1 << n); S++) {
for(int T = S; T; T = (T - 1) & S) {
if(T == S) continue;
for(int i = 1; i <= n; i++) {
int tmp = INF;
if(!(((S ^ T) >> i - 1) & 1)) continue;
for(int j = 1; j <= n; j++)
if((T >> j - 1) & 1) getmin(tmp, w[j][i]);
if(tmp == INF) {deta[T][S] = INF; break;}
deta[T][S] += tmp;
}
}
} // 预处理 deta
int ans = INF;
for(int i = 1; i <= n; i++)
getmin(ans, DP(i));
cout << ans;
}
```
#### [P2566 [SCOI2009] 围豆豆](https://www.luogu.com.cn/problem/P2566)
发现要判断豆豆是否被围住,这里用到射线定理:
> 向任意方向引一条射线,如果射线与路径的交点为奇数个,那么豆豆能被围住,反之则不能。
然后在每一个起点跑一遍最短路,要加上豆豆被围住的状态这一维。
跑最短路时要更新豆豆,我们这里向右边引一条射线,所以在上下移动时更新贡献,左右移动不更新。
更新贡献还需要满足路径在豆豆右边,且只有向上移动到豆豆哪一行或向下离开哪一行才有贡献。
然后预处理一些贡献即可。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e1 + 1;
const int M = (1 << 9);
const int fx[] = {0, 1, 0, -1, 0};
const int fy[] = {0, 0, 1, 0, -1};
int n, m, d, dd[N], dx[N], dy[N], v[M], ans;
int q[N * N * M][3], h, w, vis[N][N][M], f[N][N][M];
char a[N][N];
void bfs(int sx, int sy) {
memset(vis, 0, sizeof vis);
memset(f, 0x3f, sizeof f);
q[1][0] = sx, q[1][1] = sy;
q[1][2] = 0, h = w = 1;
vis[sx][sy][0] = 1;
f[sx][sy][0] = 0;
while(h <= w) {
int nx = q[h][0];
int ny = q[h][1];
int ns = q[h][2];
for(int i = 1; i <= 4; i++) {
int tx = nx + fx[i];
int ty = ny + fy[i];
int ts = ns;
if(a[tx][ty] != '0') continue;
if(i & 1) {
for(int j = 1; j <= d; j++) {
if(max(nx, tx) != dx[j]) continue;
if(dy[j] < ty) ts ^= (1 << j - 1);
}
} // 更新豆豆贡献
if(vis[tx][ty][ts]) continue;
f[tx][ty][ts] = f[nx][ny][ns] + 1;
vis[tx][ty][ts] = 1;
q[++w][2] = ts;
q[w][0] = tx;
q[w][1] = ty;
}
h++;
}
for(int S = 0; S < (1 << d); S++)
ans = max(ans, v[S] - f[sx][sy][S]);
}
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> d;
for(int i = 1; i <= d; i++) cin >> dd[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
int now = a[i][j] - '0';
if(now <= 0 || now > 9) continue;
dx[now] = i, dy[now] = j; // 预处理豆豆信息
}
for(int S = 0; S < (1 << d); S++)
for(int i = 1; i <= d; i++)
if((S >> i - 1) & 1) v[S] += dd[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i][j] == '0') bfs(i, j);
cout << ans;
}
```
### 轮廓线 DP
> 轮廓线用于维护已决策格子和未决策格子的分界线。
#### [P10975 Mondriaan's Dream / 蒙德里安的梦想](https://www.luogu.com.cn/problem/P10975)
轮廓线板子,维护放了一半的方块的插头,分类讨论一下即可。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e1 + 2;
int n, m, dp[2][1 << N], now;
int get(int S, int x) {return (S >> x) & 1;}
int clac(int x) {return (1 << x);}
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
while(cin >> n >> m) {
if(n == 0) return 0;
memset(dp, 0, sizeof dp); dp[now = 0][0] = 1;
for(int i = 1; i <= n; i++) {
now ^= 1;
memset(dp[now], 0, sizeof dp[now]);
for(int j = 0; j < (1 << m); j++)
dp[now][j << 1] = dp[now ^ 1][j];
for(int j = 1; j <= m; j++) {
now ^= 1;
memset(dp[now], 0, sizeof dp[now]);
for(int S = 0; S < (1 << m + 1); S++) {
if(!dp[now ^ 1][S]) continue;
int lc = get(S, j - 1); // 左插头
int uc = get(S, j); // 上插头
if(lc && uc) continue; // 方块不能是弯的。
if(!uc) dp[now][S ^ clac(j - 1)] += dp[now ^ 1][S];
if(!lc) dp[now][S ^ clac(j)] += dp[now ^ 1][S];
}
}
} cout << dp[now][0] << "\n";
}
}
```
#### [P4363 [九省联考 2018] 一双木棋 chess](https://www.luogu.com.cn/problem/P3959)
轮廓线不止能维护例题那样的轮廓,例如这题维护的是放于没放的分界线。
根据依赖的传递性,发现 $(i,j)$ 能放必须满足其左上角的矩形只有 $(i,j)$ 是空的。
设 $0$ 为竖线,$1$ 为横线,发现固定有 $n$ 个 $0$,$m$ 个 $1$,且初始 $1$ 都在右边。
发现填充一个位置相当于让一个 $1$ 往左移动一位,于是会转移了。
发现不太好枚举状态,考虑直接用记搜。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e1 + 5;
const int M = (1 << 20);
int n, m, a[N][N], b[N][N], dp[M];
void getmin(int &x, int y) {x = min(x, y);}
void getmax(int &x, int y) {x = max(x, y);}
int dfs(int sta, int now) {
if(dp[sta] < 1e9) return dp[sta];
int res = -1e9 * (now * 2 - 1), x = n + 1, y = 1;
for(int i = 0; i < n + m - 1; i++) {
if((sta >> i) & 1) x--;
else y++;
if(((sta >> i) & 3) != 1) continue;
if(now) getmax(res, dfs(sta ^ (3 << i), now ^ 1) + a[x][y]);
else getmin(res, dfs(sta ^ (3 << i), now ^ 1) - b[x][y]);
} return dp[sta] = res;
}
signed main(void) {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> b[i][j];
memset(dp, 0x3f, sizeof dp);
dp[((1 << n) - 1) << m] = 0;
cout << dfs((1 << n) - 1, 1);
}
```
#### [P5056 【模板】插头 DP](https://www.luogu.com.cn/problem/P5056)
其实和普通的轮廓线没太大区别,评黑是因为要括号匹配和分讨。
分讨见代码,不过我代码极丑,轻喷。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P = 299987;
const int K = 3e5 + 10;
const int N = 1e2 + 10;
const int M = 1ll << 25;
int n, m, a[N][N], ex, ey;
int q[M][2], s[M][2], now;
int p[N], cnt[2], ans;
int h[K], Next[K];
char str[N];
void insert(int bit, int sum) {
int u = bit % P + 1;
for(int i = h[u]; i; i = Next[i]) {
if(q[i][now] == bit) {
s[i][now] += sum;
return;
} //去重
}
Next[++cnt[now]] = h[u];
q[cnt[now]][now] = bit;
s[cnt[now]][now] = sum;
h[u] = cnt[now];
} // 可能转移到相同的状态,将方案数累加,用 hash 表的挂表法
signed main() {
scanf("%lld %lld", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%s", str + 1);
for(int j = 1; j <= m; j++) {
if(str[j] == '*') continue;
ex = i, ey = j;
a[i][j] = 1;
}
}
p[0] = 1;
for(int i = 1; i <= 20; i++)
p[i] = p[i - 1] << 2;
cnt[0] = s[1][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= cnt[now]; j++) q[j][now] <<= 2;
for(int j = 1; j <= m; j++) {
memset(h, 0, sizeof h);
int last = now;
cnt[now ^= 1] = 0;
for(int k = 1; k <= cnt[last]; k++) {
int ct = q[k][last], sum = s[k][last];
int c1 = (ct >> (j - 1) * 2) & 3;
int c2 = (ct >> j * 2) & 3;
if(!a[i][j]) { // 不能放插头
if(!c1 && !c2) insert(ct, sum);
}else if(!c1 && !c2) { // 没有插头
if(a[i + 1][j] && a[i][j + 1])
insert(ct + p[j - 1] + p[j] * 2, sum); // 新建 2 个新插头
} else if(!c1 || !c2) { // 只有一个插头
int tx = min(1ll, c1);
int ty = min(1ll, c2);
if(a[i + tx][j + ty]) insert(ct, sum); // 插头位置不变
if(a[i + ty][j + tx]) { // 插头位置改变
int ccb = c1 - c2;
int tty = p[j] * ccb;
int hkk = p[j - 1] * ccb;
insert(ct - hkk + tty, sum);
}
} else if(c1 == c2) { // 都是左插头或右插头
// 此时要合并两个线路,将剩下的插头匹配
int ks = 1;
int orz = ct - (p[j] + p[j - 1]) * c1;
if(c1 == 1) {
for(int b = j + 1; b <= m; b++) {
int ccb = (ct >> b * 2) & 3;
if(ccb) ks += 3 - ccb * 2;
if(!ks) insert(orz - p[b], sum);
if(!ks) break;
} // 匹配右括号
} else {
for(int b = j - 2; b >= 0; b--) {
int ccb = (ct >> b * 2) & 3;
if(ccb) ks += ccb * 2 - 3;
if(!ks) insert(orz + p[b], sum);
if(!ks) break;
} // 匹配左括号
// 我这写法是不是有点诡异了(
}
} else if(c1 == 2 && c2 == 1) { // 刚好一左一右
// 两个插头匹配了
insert(ct - p[j - 1] * 2 - p[j], sum);
} else if(i == ex && j == ey) ans += sum; // 到目标点了,统计答案
}
}
}
printf("%lld", ans);
}
```