Matryoshka Doll(线性DP)
参考题解:大佬题解
题目描述
题意:给定一个长度为(1~5000)的序列(单调不减),将序列分成k(1~5000)组,使得每一组内的任意两个
数字之差的绝对值均不小于r(1~1e9)。问有多少种划分方案。{{1,2}, {3,4}和{{3,4}{1,2}}认为是
同一种划分方案。
思路
设$dp[i][j]$是前$i$个物品组成$j$组且合法的方案数。
那么,对于第$i$个物品,既可以另开一组;也可以放入前面的组中。
单独开一组的方案数:$dp[i-1][j-1]$
放入前面的j组的方案怎么求呢?
首先由于数组单调,所以可以先预处理$a[i]$前有多少个数($L[i]$)和$a[i]$冲突。
也就是说:$a[1] \sim a[i-L[i]-1]$和$a[i]$不冲突,$a[i-L[i]] \sim a[i-1]$(共$L[i]$)个数和$a[i]$冲突。
重点来了:这$L[i]$个数显然也是互相冲突的,它们必然处于$L[i]$个组中。所以$a[i]$至多放入$j-L[i]$个组中,$j$是当前总的组数。
因此,放入前面$j$组的方案数:$dp[i-1][j] \times (j - L[i])$。
结果是两种方案之和。
Java 代码
package vj;
//https://vjudge.net/problem/HDU-7239
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class MatryoshkaDoll {
static BufferedWriter writter = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static final int N = 5005, MOD = 998244353;
static int t, n, k, r;
static int[] a = new int[N]; // sorted, index从1开始
// L[i]表示a[i]左边共有L[i]个数和它不相容。易知,这L[i]个数也互不相容。
static int[] L = new int[N];
static long[][] dp = new long[N][N]; // 前i个数字,分为j组且构成俄罗斯套娃的方案数
public static void main(String[] args) throws IOException {
t = Integer.parseInt(reader.readLine());
while(t-- > 0)
{
String[] readStrings = reader.readLine().split(" ");
n = Integer.parseInt(readStrings[0]);
k = Integer.parseInt(readStrings[1]);
r = Integer.parseInt(readStrings[2]);
readStrings = reader.readLine().split(" ");
for (int i = 1; i <= n; i++)
{
a[i] = Integer.parseInt(readStrings[i-1]);
L[i] = 0;
for(int j=i-1; j>=1; j--)
if(a[i] - a[j] < r)
L[i] ++;
else break;
}
for (int i = 0; i <= n; i++)
Arrays.fill(dp[i], 0);
// dp[i][j]只依赖dp[i-1][j]和dp[i-1][j]
// 为了不用单独求dp[1][...],需要初始化dp[0][0~n]
// 其中,dp[0][1~n]显然非法,置为0
// 为了让dp[1][1]=1, 需要让dp[0][0]=1
dp[0][0] = 1; // ?
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
// max (物品i新开一个组, 物品i放入现有的j个组)
// 由于有L[i]个数和a[i]不相容,且它们本身要占L[i]个组,因此物品i最多可能被放入已有的(j-L[i])个组
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (j - L[i])) % MOD;
}
}
writter.write(dp[n][k]+"\n");
}
writter.close();
reader.close();
}
}