逆序对数列-dp前缀和优化

逆序对数列-dp前缀和优化

逆序对数列
加强版+数学

思路

如果按位置来 dp ，显然不方便转移，发现我们插入一个数之后，才会有不同的个数产生。我们考虑从 \(1\) 到 \(n\) 不断插入，我们产生的个数就是从 \(0\) 到 \(i\) ，设计状态 \(dp[i][j]\) 表示插入 \(i\) 之后，产生的逆序对数为 \(j\) 的个数，它的转移有 \(dp[i][j]=dp[i-1][j-k] | k \leq i\) 发现 \(j\) 可能比 \(i\) 小，这时候的转移就是 $\sum_{k \leq j} dp[i-1][k] $

此时时间复杂度为 \(O(n^3)\) 显然会 TLE，发现这个 \(\sum\) 可以前缀和优化，得到 \(O(nk)\) 。至于再优化。。之后再说吧。

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 1e3+10;
constexpr int mod = 1e4;int n,k;
int dp[maxn][maxn];
int sum[maxn];// i-1 的前缀和signed main()
{#ifndef ONLINE_JUDGEfreopen("cjdl.in","r",stdin);freopen("cjdl.out","w",stdout);#endif // ONLINE_JUDGEscanf("%lld%lld",&n,&k);dp[0][0]=1;// 0 个逆序对的可能为1for(int i=0;i<=k;++i)// 0 对应的前缀和{sum[i]=1;}for(int i=1;i<=n;++i){for(int j=0;j<=k;++j){if(j>=i){dp[i][j]=(sum[j]-sum[j-i]+mod)%mod;}else{dp[i][j]=sum[j];}}sum[0]=dp[i][0];for(int j=1;j<=k;++j)// 前缀和{sum[j]=(dp[i][j]+sum[j-1])%mod;}}printf("%lld\n",dp[n][k]);return 0;
}