51nod 1250 排列與交換——dp

題目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1250

仔細思考dp。

第一問，考慮已知 i-1 個數有多少種方案。再放入一個數，它是最大的且在最后面，所以它的位置不同的話，就是不同的方案。它在特定的位置，其余部分的值就是 i-1 的值。

　　所以再用前綴和優化成 n^2 即可。k可減任意個2。

第二問，還是像上面一樣考慮。但新來的數只會和前面的數交換一次。任何一種交換 k ( k>1 ) 次的方案都可以轉換成前面的數先交換 k-1 次，再由新來的數交換一次。所以就能很方便地dp了。

還可以從逆序對的角度考慮第一問、從斯特林數的角度考慮第二問。反正式子是一樣的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=3005,mod=1e9+7;
int n,k,dp[2][N],c[2][N],ans,u,v;
int main()
{scanf("%d%d",&n,&k);dp[1][0]=1;for(int i=0;i<=k;i++) c[1][i]=1;u=0;v=1;for(int i=2;i<=n;i++){for(int j=0;j<=k;j++){dp[u][j]=(c[v][j]-(j-i>=0?c[v][j-i]:0)+mod)%mod;c[u][j]=(dp[u][j]+(j?c[u][j-1]:0))%mod;}u=!u;v=!v;}for(int i=k;i>=0;i-=2) (ans+=dp[v][i])%=mod;printf("%d ",ans); ans=0;u=0;v=1;memset(dp[1],0,sizeof dp[1]); dp[1][0]=1;for(int i=2;i<=n;i++){for(int j=0;j<=k;j++)dp[u][j]=(dp[v][j]+(j?(ll)dp[v][j-1]*(i-1)%mod:0))%mod;u=!u;v=!v;}for(int i=0;i<=k;i++) (ans+=dp[v][i])%=mod;printf("%d\n",ans);return 0;
}

?