[haoi2009]逆序对数列-白红宇

[haoi2009]逆序对数列

阅读量：5272 次

发布时间：2019-06-14

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

对于一个数列{ai}，如果有i<j且ai>aj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个?

n<=1000，k<=1000

题解：很明显的动态规划题目；

设f[i][j]表示使长度为i的，只含数字1-i的序列，逆序对数有j个的方案数；

我们在转移的时候很好操作，假如此时正在求f[i][j]，那么我们枚举这个1-i序列的最后一位数字，假设这个数字是k，那么f[i][j]+=f[i-1][j-(i-k)]，i-k表示若最后一位数字为k对逆序对的贡献；

这么搞是O(n²m)的，1000的数据量会T；

可以看到每次f[i][j]的结果是f[i-1]的结果中的一段和，那么就可以记录下当前的sum=(f[i-1][head]+f[i-1][head+1]...+f[i-1][tail])，这样每次换j的时候调整一下区间的左右端点就好了；

总复杂度O(nm);

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define FILE "1"#define LL long long #define up(i,j,n) for(int i=j;i<=n;i++)#define pii pair
                 
                  #define piii pair
                  
                   
                     >template
                    
                      inline bool chkmin(T &a,T b){ return a>b?a=b,true:false;}template
                     
                       inline bool chkmax(T &a,T b){ return a
                      
                       '9'){ if(ch=='-')f=1;ch=gc();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();} return f?-x:x; }}using namespace IO;namespace OI{ const int maxn(1100),mod(10000); int f[maxn][maxn]; int n,m; void slove(){ n=read(),m=read(); f[1][0]=1; for(int i=2;i<=n;i++){ int sum=0,head=0,tail=-1; f[i][0]=1; for(int j=1;j<=m;j++){ while(j-i+1>head)sum=(sum-f[i-1][head]+mod)%mod,head++;//控制左右端点的移动 while(tail

转载于:https://www.cnblogs.com/chadinblog/p/6000889.html

你可能感兴趣的文章