題目描述：
1...n的排列 p1 ... pn ，位置 i 是good，當且僅當 abs(pi - i) = 1。 問大小為N ，恰好有K個位置是good的排列是多少？
算法分析：
非常好的一道題，O(n^2) DP搞之。
dp[n][k][p][q] 代表 大小為n，有k個good位置，p ＝ 1代表 倒數第二個位置是n - 1 ，p = 2代表倒數第二個位置是 n， p = 0代表其他，q代表最后一個位置。
然后轉移不難想。。。。
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define re(i,n) for(int i = 0; i < n; i++)
5 typedef long long ll;
6 const int N = 1005;
7 const int mod = (int)1e9+7;
8 ll dp[N][N][3][3];
9 int main(){
10 int n,k;
11 cin >> n >> k;
12 dp[1][0][0][1] = 1;
13 dp[2][0][1][2] = 1;
14 dp[2][2][2][1] = 1;
15 for(int i = 3; i <= n; i++){
16 for(int k = 0; k <= i; k++) {
17 // * 2
18 re(p,2) re(q,3) dp[i][k][p][2] += dp[i-1][k][q][p+1];
19 re(q,3) dp[i][k][0][2] += dp[i-1][k][q][0];
20 // 2 1
21 if(k >= 2) re(q,2) dp[i][k][2][1] += dp[i-1][k-2][q][2];
22 // 2 0
23 re(q,3) dp[i][k][2][0] += dp[i-1][k][q][1];
24 if(k >= 1) re(q,3) dp[i][k][2][0] += dp[i-1][k-1][q][0];
25 // 0 1
26 dp[i][k][0][1] += dp[i-1][k][2][1] + dp[i-1][k][2][0];
27 if(k >= 1) dp[i][k][0][1] += dp[i-1][k-1][0][0] + dp[i-1][k-1][0][1] + dp[i-1][k-1][1][0];
28 // 1 0
29 re(q,2) dp[i][k][1][0] += dp[i-1][k+1][q][2] * (k + 1);
30 if(i - 2 - k >= 0) re(q,2) dp[i][k][1][0] += dp[i-1][k][q][2] * (i - 2 - k);
31 // 0 0 vs 2 1
32 ll &ans = dp[i][k][0][0];
33 if(k - 1 >= 0) ans += dp[i-1][k+1][2][1] * (k - 1) ;
34 if(i - 1 - k >= 0) ans += dp[i-1][k][2][1] * (i - 1 - k);
35 // cout<<"vs 2 1: "<<i<<" "<<k<<" "<<ans<<endl;
36 // 0 0 vs 2 0
37 ans += dp[i-1][k + 1][2][0] * k;
38 if( i - 2 - k >= 0) ans += dp[i-1][k][2][0] * (i - 2 - k);
39 // cout<<"vs 2 0: "<<i<<" "<<k<<" "<<ans<<endl;
40 // 0 0 vs * 2
41 // re(q,2) ans += dp[i-1][k+1][q][2] * (k + 1);
42 // re(q,2) if(i - 2 - k >= 0)ans += dp[i-1][k][q][2] * (i - 2 - k);
43 // 0 0 vs * 0
44 re(q,2) ans += dp[i-1][k+1][q][0] * (k + 1);
45 if(i - 3 - k >= 0) re(q,2) ans += dp[i-1][k][q][0] * (i - 3 - k);
46 // cout<<"vs * 0: "<<i<<" "<<k<<" "<<ans<<endl;
47 // 0 0 vs 0 1
48 ans += dp[i-1][k+1][0][1] * k;
49 if(i - 2- k >= 0) ans += dp[i-1][k][0][1] * (i - 2 - k);
50 // cout<<"vs 0 1: "<<i<<" "<<k<<" "<<ans<<endl;
51 re(p,3) re(q,3) dp[i][k][p][q] %= mod;
52 }
53 }
54 ll ans = 0;
55 re(q,3) re(p,3){
56 ans += dp[n][k][p][q];
57 // cout<<p<<" "<<q<<" "<<dp[n][k][p][q]<<endl;
58 }
59 // int a,b,c,d; while(cin >> a >> b >> c >> d) cout<<dp[a][b][c][d]<<endl;
60 cout << ans % mod << endl;
61 }
62
posted on 2013-03-22 16:11
西月弦 閱讀(333)
評論(0) 編輯 收藏 引用