这题我和王队合力做,王队想到了第一个转化,我想到了第二个转化,但是并没有导出成型的做法,看来,关键时候的坚持确实十分重要。
不要被难度标签所吓到。现在来看,我每次都能隐约想到正解的一些东西,但难出做法,很可能是对算法理解不够深入。
但又该怎么提升呢?也许多做题是有用的。我也能感觉得出来,最近做的题质量有提升。希望这是好的开始。
首先,这题在圆上和在序列上做是没有区别的,两条在圆上相交的线段在序列上也是相交的,反之亦然。
那么,在序列上,线段相当于一段区间,而一堆有交的线段,看上去就像一个大区间。
事实上,对于一个连通块,我们考察其最左边的点 和最右边的点 ,一个连通块显然对应一个区间。
都观察到这里了,我居然想设计一个从前向后的 DP(
看来思考的时候,在草稿纸上写清楚已有的结论至关重要。
设 表示对应区间为 的连通块数,并附加限制:且 中没有点向
之外连边(包括我们所计数的连通块,也包括这个连通块以外,但在 中的点)。
设 表示 个点任意匹配的方案数,在 为偶数时,其为 ,在 为奇数时其为 。
设 表示区间
内还未确定匹配的点数(就是输入中未涉及到的点)。
首先,如果 ,那么 。
如果读者熟悉图计数的话,会知道一个计数连通块的套路:总方案减去 “ 号点所在连通块大小小于总数”
的方案。
这里也是要计数连通块,我们也还是先让 。
然后枚举 号点所在连通块不是
的方案数,即
综上所述,有转移式: 。
最后的答案就是 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include <bits/stdc++.h> using namespace std; const int N = 6e3 + 5,P = 1e9 + 7; int n,K; int g[N],match[N]; int dp[N][N],sum[N]; inline int Cnt(int l,int r) { return sum[r] - sum[l - 1];}
int main() { cin >> n >> K;n <<= 1; for(int i = 1;i <= K;i++) { int u,v; cin >> u >> v; match[u] = v;match[v] = u; } for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + (!match[i]); g[0] = 1; for(int i = 2;i <= n;i += 2) g[i] = 1ll * g[i - 2] * (i - 1) % P; int ans = 0; for(int len = 2;len <= n;len += 2) for(int i = 1;i + len - 1 <= n;i++) { int j = i + len - 1,flag = 1; for(int x = i;x <= j;x++) if(match[x] && (match[x] < i || match[x] > j)) { flag = 0;break;} if(!flag) continue; dp[i][j] = g[Cnt(i,j)]; for(int k = i;k < j;k++) dp[i][j] = (dp[i][j] + P - 1ll * dp[i][k] * g[Cnt(k + 1,j)] % P) % P; ans = (ans + 1ll * dp[i][j] * g[n - 2 * K - Cnt(i,j)] % P) % P; } cout << ans << endl; return 0; }
|