题意:求逆序对数量为k的长度为n的排列的个数

SOL:

  显然我们可以对最后一位数字进行讨论,判断其已经产生多少逆序对数量,然后对于前n-1位同样考虑---->每一个长度的排列我们都可以看做是相同的,因为它与最后一位的影响我们已经计算过了.那么就变成了一个好多维DP的过程...

  不过我的方程感觉有点太直白,应该可以优化因为在BZ上都是卡时过去的...太慢了...大概状态还是有问题....

Code:  

/*=================================================================
# Created time: 2016-03-30 19:36
# Filename: 2431.cpp
# Description:
=================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define mod 10000
#define maxn 1100
#define maxk 1010
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
int f[maxn][maxk];
int main(){
int n,k;
read(n); read(k);
memset(f,0,sizeof(f));
f[1][0]=1;
FORP(i,1,n)
FORP(j,1,i) {
int t=i-j;
FORP(l,0,k-t)
f[i][l+t]+=f[i-1][l],f[i][l+t]%=mod;
}
printf("%d\n",f[n][k]);
}

最新文章

  1. iOS thirdKeyboard Develop (APP Extension)
  2. Android 4.0 源代码结构
  3. Java面向对象编程之异常处理机制
  4. 简进祥--iOS开发基础知识
  5. .net如何把导数据入到Excel
  6. 【wikioi】1690 开关灯(线段树)
  7. Jar mismatch! Fix your dependencies
  8. BZOJ_1623:_[Usaco2008_Open]_Cow_Cars_奶牛飞车_(贪心)
  9. 软件授权协议有什么作用,例如GPL、Apache License、CDDL、EPL这些协议有什么区别?
  10. sql 作业+游标 自动备份数据库
  11. swift2.0 UIImagePickerController 拍照 相册 录像
  12. Android消息机制不完全解析(下)
  13. SpringMVC框架学习笔记(1)——HelloWorld
  14. react-router v4中 HashRouter 和 BrowserRouter的使用
  15. ASP.NET之虚方法
  16. mysql左连接
  17. sqlAlchemy语法增删改查
  18. python并发(阻塞、非阻塞、epoll)
  19. swoole web服务
  20. Kafka.net使用编程入门(一)

热门文章

  1. Spring task定时任务
  2. 简单的STM32 汇编程序—闪烁LED
  3. 深入理解javascript原型和闭包(5)——instanceof
  4. NOIP2012同余方程
  5. HDU 1003 maxsum
  6. jQuery入门(4)jQuery中的Ajax应用
  7. java基础知识(二)字符串处理
  8. JVM参数OmitStackTraceInFastThrow:不打印NullPointerException异常堆栈
  9. Android 组件和进程的一些关系
  10. 【Eclipse】总结自己在工作中经常使用到的Eclipse快捷键