[luoguP2513] [HAOI2009]逆序对数列(DP)
2024-09-08 01:39:11
f[i][j]表示前i个数,逆序对数为j的答案
则DP方程为:
f[1][0] = 1;
for(i = 2; i <= n; i++)
for(j = 0; j <= m; j++)
for(k = j; k < j + i; k++)
f[i][k] = (f[i][k] + f[i - 1][j]) % p;
但是会超时
所以搞个前缀和优化一下
#include <cstdio>
#include <iostream>
#define N 2001
#define p 10000 int n, m;
int f[N][N], sum[N][N]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} int main()
{
int i, j, k;
n = read();
m = read();
f[1][0] = 1;
for(i = 0; i <= m; i++) sum[1][i] = 1;
for(i = 2; i <= n; i++)
for(j = 0; j <= m; j++)
{
if(j - i + 1 > 0)
f[i][j] = (f[i][j] + ((sum[i - 1][j] - sum[i - 1][j - i]) % p + p) % p) % p;
else
f[i][j] = (f[i][j] + sum[i - 1][j]) % p;
sum[i][j] = (sum[i][j - 1] + f[i][j]) % p;
}
printf("%d\n", f[n][m]);
return 0;
}
最新文章
- 细细品味Storm_Storm简介及安装
- Mysql修改root用户密码 For Mac 报错:ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: NO)
- BZOJ 1034 题解
- vi/vim基本使用方法
- [置顶] 1D1D动规优化初步
- 用RestTemplate碰到的问题
- BPMN2新规范与Activiti5
- UVa 437 (变形的LIS) The Tower of Babylon
- Codeforces Round #185 (Div. 2) B. Archer 水题
- Best Practices for Using Alpha
- HDOJ/HDU 2087 剪花布条(indexOf()应用~~)
- IOS 企业版证书($299)In-House方式发布指南
- 基于visual Studio2013解决C语言竞赛题之0524职工年龄
- leetcode day6 -- String to Integer (atoi) &;amp;&;amp; Best Time to Buy and Sell Stock I II III
- 使用cacti监控服务器
- js学习要点
- 堆排序(Java数组实现)
- XamarinForm Effects 调用事件
- bsp总结
- QT动态库和静态库使用