洛谷P2401 不等数列(线性DP)

本题使用的是线性DP。就是DP数组难以思考，这里我直接给出

dp[i][j]：表示 1 ~ i 这 i 个数 , 其中j 个 " < " 有几种方法

假设我们已经把 n - 1 个数排好了，现在我们要在其中插入第 n 个数，n 大于这个数列中的任何数

若 n 插在第一个数之前，因为它比第一个数大，则多一个 " > "

若 n 插在最后一个数之后，同上，多了一个 " < "

若 n 插在 " < " 之前，因为它比 " < " 之后的数大，所以 " < " 变成 " > "，而它比前面的那个数大，所以它前面添加了一个 " < " . 综合来看，多了一个 " > "; Example: 2 < 4 ----> 2 < 5 > 4

若 n 插在 " > "，同上，多了一个 " < "

用状态转移方程，则表示为：

dp[ i ] [ j ] = dp [ i-1 ] [ j ]： " < " 个数没变，所以 j 不变，而插入一个数，数是比之前多 1 的

dp [ i ] [ j ] = dp[ i - 1 ] [ j - 1 ]：多了一个数，又多了一个 " < "

dp[ i ] [ j ] = dp [ i - 1 ] [ j ] * j：" < " 个数没变，所以 j 不变；但是 n 可以插在这 j 个 " < "中的任意一个之前，所以方案数增多 j 个

dp[ i ] [ j ] = dp[ i - 1 ] [ j - 1 ] * ( i - j -1 )：与上同理，不过这次是插在 " > " 之前了，因此方案增多数等于 " > " 个数，也就是总的符号个数 ( i - 1 )，减去 " < "的个数 ( j )，也就是 ( i - j -1 )

合并同类项，可得：

f [ i ] [ j ] = ( f [ i - 1 ] [ j - 1 ] x ( i - j ) % 2015 + f [ i - 1 ] [ j ] x ( j + 1 ) % 2015 ) % 2015

#include<iostream> using namespace std; const int N=1e3+5; const int mod=2015; int n,k; int dp[N][N]; int main() {scanf("%d%d",&n,&k);dp[1][0]=1;for(int i=2;i<=n;++i){dp[i][0]=1; //前i个数0个<号的情况只有1种，即单调上升。 for(int j=1;j<=k;++j){dp[i][j]=(dp[i-1][j-1]*(i-j)%mod+dp[i-1][j]*(j+1)%mod)%mod;}}printf("%d",dp[n][k]);return 0; }

总结

以上是生活随笔为你收集整理的洛谷P2401 不等数列(线性DP)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。