[HAOI2009]逆序对数列【线性DP】

传送门 我们发现逆序数可以有前一个转换而来 假设由$dp[i][j]$表示全排列中逆序数为j的个数 考虑在$i-1$的排列中插入i。k是这次更新辉导致增加多少逆序数 则有$$dp[i][j]=\sum _{k=0}^{min(i-1,j)}dp[i-1][j-k]$$ 等价于$$dp[i][j]=\sum _{k=min(0,j-i+1)}^{j}dp[i-1][j-k]$$ 超时了

code:

#include<bits/stdc++.h> using namespace std; int n,m; int dp[1005][1005]; int ans=0; int main(){ cin>>n>>m; dp[1][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=min(i-1,j);k++){ dp[i][j]+=dp[i-1][j-k]; dp[i][j]%=10000; printf("dp[%d][%d]=%d\n",i,j,dp[i][j]); } printf("%d\n",dp[n][m]); }

仔细发现，$dp[i][j]$是由$dp[i-1]$的前缀转化而来的，因此每次枚举i之后，我们维护一个叫做sum来表示$dp[i-1]$的前缀和然后就能$O(n^2)$转移了。

code:

#include<bits/stdc++.h> using namespace std; int n,m; int dp[1005][1005]; int sum[1005][1005]; int ans=0; int main(){ scanf("%d%d",&n,&m); //n=1000,m=1000; dp[1][0]=1; sum[1][0]=1; for(int i=1;i<=m;i++) sum[1][i]=sum[1][i-1]; for(int i=2;i<=n;i++){ dp[1][i]=dp[i-1][0]; for(int j=0;j<=m;j++){ int tmp=min(i-1,j); dp[i][j]=(sum[i-1][j]-sum[i-1][j-tmp-1]+10000)%10000; } sum[i][0]=dp[i][0]; for(int j=1;j<=m;j++) sum[i][j]=(sum[i][j-1]+dp[i][j])%10000; } printf("%d\n",dp[n][m]); }

空间优化sum… code:

#include<bits/stdc++.h> using namespace std; int n,m; int dp[1005][1005]; int ans=0; int main(){ scanf("%d%d",&n,&m); // n=1000,m=1000; dp[1][0]=1; for(int i=2;i<=n;++i){ ans=0; for(int j=0;j<=m;++j){ ans=(ans+dp[i-1][j])%10000; dp[i][j]=ans%10000; if(j+1-i>=0)ans=(ans-dp[i-1][j-i+1]+10000)%10000; } } printf("%d\n",dp[n][m]); }