d[u][v] : 用v - u次交换把第u个至第v个变成升序的方法数
t[u][k][v] : 最后一次交换k, k + 1两个位置的数的方法数
可见,
d[u][v] = sum{t[u][k][v] | k = u, .., v - 1}
t[u][k][v] = zh[v - u - 1][k - u] * d[u][k] * d[k + 1][v]
两个状态相互推算!!
递归写法思路比较清晰.
class AdjacentSwaps {
public:
int theCount(vector <int>);
};
const int mod = 1000000007;
const int N = 55;
int zh[N][N];
int d[N][N], t[N][N][N];
int a[N];
int n;
void cal_zh() {
int i, j, k;
for (i = 0; i < N; ++i) {
zh[0][i] = 0;
zh[i][0] = 1;
}
for (i = 1; i < N; ++i) {
for (j = 1; j < N; ++j) {
zh[i][j] = (zh[i - 1][j] + zh[i - 1][j - 1]) % mod;
}
}
}
void cal_t(int u, int v, int t);
void cal_d(int u, int v);
void cal_t(int u, int k, int v) {
int i, j;
if (t[u][k][v] != -1) return;
int tmin = N, tmax = -1;
for (i = u; i <= k; ++i) {
tmax = max(tmax, a[i]);
}
for (i = k + 1; i <= v; ++i) {
tmin = min(tmin, a[i]);
}
bool work = true;
for (i = u; i <= k; ++i) {
if (tmax == a[i]) continue;
if (tmin < a[i]) work = false;
}
for (i = k + 1; i <= v; ++i) {
if (tmin == a[i]) continue;
if (tmax > a[i]) work = false;
}
if (!work || tmin > tmax) {
t[u][k][v] = 0;
return ;
}
cal_d(u, k);
cal_d(k + 1, v);
t[u][k][v] = (long long) zh[v - u - 1][k - u] * d[u][k] % mod
* d[k + 1][v] % mod;
}
void cal_d(int u, int v) {
int i, j, k;
if (d[u][v] != -1) return ;
if (u == v) {
d[u][v] = 1;
return ;
}
d[u][v] = 0;
for (i = u; i < v; ++i) {
cal_t(u, i, v);
d[u][v] += t[u][i][v];
d[u][v] %= mod;
}
}
int AdjacentSwaps::theCount(vector <int> p) {
cal_zh();
n = p.size();
for (int i = 0; i < n; ++i) {
a[i] = p[i];
}
memset(d, -1, sizeof(d));
memset(t, -1, sizeof(t));
cal_d(0, n - 1);
return d[0][n - 1];
}
补充:
第一个和最后一个往往是dp状态的突破口,例如这个问题中t[u][k][v]k表示最后操作的位置。
分享到:
相关推荐
该文件共分12个压缩包,必须下载到同一个文件夹后解压才可以用哦~~ 简介: 《TCP/IP详解,卷1:协议》是一本完整而详细的TCP/IP协议指南。描述了属于每一层的各个协议以及它们如何在不同操作系统中运行。...
该文件共分12个压缩包,必须下载到同一个文件夹后解压。 简介: 《TCP/IP详解,卷1:协议》是一本完整而详细的TCP/IP协议指南。描述了属于每一层的各个协议以及它们如何在不同操作系统中运行。...
目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 ...16.13 select系统...
整套电子书分四部分上传 TCP-IP详解卷1.rar;TCP-IP详解卷2_1.rar TCP-IP详解卷2_2.rar;TCP-IP详解卷3.rar 都上传了。只下第一部分不全 目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 ...16.11...
《TCP-IP详解》共3卷,其他卷请到我空间下载,第2卷共分两个part,请下载完两个part后在解压。本书完整而详细地介绍了TCP/IP协议是如何实现的。书中给出了约500个图例,15 000行实际操作的C代码,采用举例教学的方法...
第一部分 Oracle SQL*PLUS基础 23 第一章 Oracle数据库基础 23 §1.1 理解关系数据库系统(RDBMS) 23 §1.1.1 关系模型 23 §1.1.2 Codd十二法则 24 §1.2 关系数据库系统(RDBMS)的组成 24 §1.2.1 RDBMS 内核 24...
A Lock Service 517 More Distributed Data Structures and Protocols 519 ZooKeeper in Production 520 Resilience and Performance 521 Configuration 522 15. Sqoop . . . . . . . . . . . . . . . . . . . . . ....
rem rem $Header: summit2.sql 27-jun-2000.12:30:22 slari Exp $ rem ... All rights reserved. rem rem NAME rem summit2.sql - rem DESCRIPTION rem rem RETURNS ...rem Create and populate tables and sequences to...
TCPIP协议详解卷2:实现 pdf版,有目录,完美阅读体验。 中文书名:TCP/IP详解 卷2:实现 英文书名:TCP/IP Illustrated, Volume 2: The Implementation 作者:(美) Gary R. Wright ,W....译者:陆雪莹、蒋慧 等译;...
第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 1.8 描述符 7 ...
第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 ...
第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 ...
第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 ...
第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 ...
目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 ...16.13 select系统...
目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 ...16.13 select系统...
目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 ...16.13 select系统...
目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 ...16.13 select系统...
目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 ...16.13 select系统...
目 录 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 ...16.13 select系统...