洛谷 P2513 ——逆序对数列

题目描述
对于一个数列 { a i } {a_i} {ai​}，如果有 i < j i a j a_i>a_j ai​>aj​，那么我们称 a i a_i ai​ 与 a j a_j aj​ ​ 为一对逆序对数。

若对于任意一个由 1 ∼ n 1∼n 1∼n 自然数组成的数列，可以很容易求出有多少个逆序对数。

那么逆序对数为 k k k 的这样自然数数列到底有多少个？

输入格式
第一行为两个整数 n ， k n，k n，k。

输出格式
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对 10000 10000 10000 求余数后的结果。

输入样例
4 1

输出样例
3

样例说明
下列 3 3 3 个数列逆序对数都为 1 1 1，分别是:

• 1 2 4 3 ；
• 1 3 2 4 ；
• 2 1 3 4；

数据范围
n ， k ≤ 1000 n，k≤1000 n，k≤1000

题解一（超时）：线性DP

f [ i ] [ j ] ： 由 1 ∼ i 组 成 的 逆 序 对 数 量 为 j 的 数 列 个 数 f[i][j]：由1∼i组成的逆序对数量为j的数列个数 f[i][j]：由1∼i组成的逆序对数量为j的数列个数

状 态 转 移 ： 状态转移： 状态转移：

• 考 虑 第 i 个 数 的 放 置 情 况 ， 由 于 i 的 数 值 最 大 ， 因 此 根 据 不 同 的 放 置 位 置 ， 可 以 产 生 的 逆 序 对 数 量 为 0 ∼ i − 1 考虑第i个数的放置情况，由于i的数值最大，因此根据不同的放置位置，可以产生的逆序对数量为0∼i-1 考虑第i个数的放置情况，由于i的数值最大，因此根据不同的放置位置，可以产生的逆序对数量为0∼i−1
• 因 此 f [ i ] [ j ] + =   ∑ r = j − ( i − 1 ) j ( f [ i − 1 ] [ r ] ) 因此f[i][j]+= sum_{r=j-(i-1)}^{j}{(f[i-1][r])} 因此f[i][j]+= ∑r=j−(i−1)j​(f[i−1][r])

#include 
using namespace std;

const int N = 1010, MOD = 1e4;

int n, k;
int dp[N][N];

int main()
{
	cin >> n >> k;
	
	dp[1][0] = 1;
	for (int i = 2; i <= n; i ++)
		for (int j = 0; j <= k; j ++)
			for (int r = j - (i - 1); r <= j; r ++)
				if(r >= 0) 
					dp[i][j] = (dp[i][j] + dp[i - 1][r]) % MOD;
				
	cout << dp[n][k] << endl;
	return 0;			
}

题解二：线性DP（优化）

• 由 于 是 从 j 开 始 ， 往 前 数 连 续 i 个 数 由于是从j开始，往前数连续i个数 由于是从j开始，往前数连续i个数
• 因 此 ， 当 计 算 f [ i ] [ j + 1 ] 的 时 候 ， 是 在 f [ i ] [ j ] 的 基 础 上 ， 要 先 加 上 f [ i − 1 ] [ j + 1 ] ， 再 减 去 f [ i − 1 ] [ j − ( i − 1 ) ] 因此，当计算f[i][j+ 1]的时候，是在f[i][j]的基础上，要先加上f[i-1][j+1]，再减去f[i-1][j-(i-1)] 因此，当计算f[i][j+1]的时候，是在f[i][j]的基础上，要先加上f[i−1][j+1]，再减去f[i−1][j−(i−1)]
• 所 以 在 计 算 f [ i ] [ j ] 时 ， 要 先 加 上 f [ i − 1 ] [ j ] ， 再 减 去 f [ i − 1 ] [ j − i ] 所以在计算f[i][j]时，要先加上f[i-1][j]，再减去f[i-1][j-i] 所以在计算f[i][j]时，要先加上f[i−1][j]，再减去f[i−1][j−i]

f[i][j]     = f[i - 1][j - (i - 1)] + f[i - 1][j - (i - 2)] + ... + f[i - 1][j - 1] + f[i - 1][j]
f[i][j + 1] =                         f[i - 1][j - (i - 2)] + ... + f[i - 1][j - 1] + f[i - 1][j] + f[i - 1][j + 1]

#include 
using namespace std;

const int N = 1010, MOD = 1e4;

typedef long long LL;

int n, k;
int dp[N][N];

int main()
{
	cin >> n >> k;
	
	dp[1][0] = 1;
	for (int i = 2; i <= n; i ++)
	{
		LL sum = 0;
		for (int j = 0; j <= k; j ++)
		{
			sum += dp[i - 1][j];
			if(j - i >= 0) sum -= dp[i - 1][j - i];
			dp[i][j] = sum % MOD;
		}
	}
				
	cout << dp[n][k] << endl;
	return 0;			
}