集团网站建设哪个好,seo网络优化公司排名,吉林建筑大学本科招生网,优化培训内容题目链接 这种求方案数的题一般都是\(dp\)吧。 注意到范围里\(k\)和\(n\)的范围一样大#xff0c;\(k\)是完全可以更大的#xff0c;到\(n\)的平方级别#xff0c;所以这暗示了我们要把\(k\)写到状态里。\(f[i][j]\)表示前\(1\)~\(i\)的排列逆序对数为\(j\)的方案数。 现在考…题目链接 这种求方案数的题一般都是\(dp\)吧。 注意到范围里\(k\)和\(n\)的范围一样大\(k\)是完全可以更大的到\(n\)的平方级别所以这暗示了我们要把\(k\)写到状态里。\(f[i][j]\)表示前\(1\)~\(i\)的排列逆序对数为\(j\)的方案数。 现在考虑把\(i\)插入到\(i-1\)的排列里。\(i\)肯定是大于\(1\)~\(i-1\)所有数的所以插入\(i\)后可以新产生\(0\)~\(i-1\)个逆序对。 于是就能写出\(O(n^3)\)的\(dp\)算法了。 像这种转移范围是个区间的要优化不是单调队列就是前缀和当然是愉快地选择后者啦。 #include queue
#include cstdio
#include cstring
#include algorithm
using namespace std;
#define Open(s) freopen(s.in,r,stdin);freopen(s.out,w,stdout);
#define Close fclose(stdin);fclose(stdout);
int n, k; int f[1010][1010];
const int MOD 10000;
int main(){scanf(%d%d, n, k);f[1][0] 1;for(int i 2; i n; i){int sum 0;for(int j 0; j k; j){sum (sum f[i - 1][j]) % MOD;f[i][j] sum;if(j i - 1)sum ((sum - f[i - 1][j - i 1]) % MOD MOD) % MOD;}}printf(%d\n, f[n][k]);return 0;
}转载于:https://www.cnblogs.com/Qihoo360/p/9901351.html
