hdu3664（递推dp）-白红宇

hdu3664（递推dp）

阅读量：5949 次

发布时间：2019-06-19

本文共 790 字，大约阅读时间需要 2 分钟。

题目链接：

分析：dp[i][j]表示i个数的排列中E值为j的个数。假设现在已有一个E值为j的i的排列，对于新加入的一个数i+1,将其加入排列的方法有三：

1)把它放最后，加入后E值不变

2)把它和一个满足A[k]>k的数交换，A[k]到最后，A[k]必定小于i+1，交换后E值不变，符合这样的k共有j个

3)把它和一个不满足A[k]>k的数交换，A[k]到最后，A[k]必定小于i+1，交换后E值+1，符合这样的k共有i-j个

根据这三种方法得到转移方程dp[i][j] = dp[i - 1][j] + dp[i - 1][j] * j + dp[i - 1][j - 1] * (i - j);

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define LL long long#define inf 1<<30#define mod 1000000007using namespace std;LL f[1010][1010];void init(){ for (int i=1;i<=1000;i++) { f[i][0]=1; for (int j=1;j
                
                 0) printf("%I64d\n",f[n][k]); return 0;}