题解 P2513 【[HAOI2009]逆序对数列】
「QQ红包」
2017-09-01 09:45:35
用$dp[i][j]$ 表示$1-i$个数,逆序对数为j时的方案数
最后一个数字如果插在第$0$ 个位置,那么逆序对数将增加$i-1$对,插在第$1$个位置逆序对将增加$i-2$ 对.
于是可以很简单的推出状态转移方程了
```cpp
for (int i=1;i<=n;i++)
{
f[i][0]=1;
for (int j=1;j<=k;j++)
{
for (int l=max(1,i-j);l<=i;l++)
{
f[i][j]+=f[i-1][j-i+l];
}
f[i][j]%=10000;
}
}
```
然后提交看一下是不是对的.
啥?! A了?! 这数据太水.
然后可以发现,每次转移都是某一段的和,然后可以用前缀和搞,这样每次转移就是O(1)
$s[i][j]$表示$f[i][0]$~$f[i][j]$的和
我分了2类,其实并不需要?因为出现了减法,所以取模的时候要注意下
```cpp
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,k;
int f[1010][1010];
int s[1010][1010];//s[i][j]表示f[i][0]~f[i][j]的和
int main()
{
n=read();k=read();
for (int i=1;i<=n;i++)
{
f[i][0]=1;
s[i][0]=1;
for (int j=1;j<=k;j++)
{
/*for (int l=max(1,i-j);l<=i;l++)
{
f[i][j]+=f[i-1][j-i+l];
}*///手推一下就可以推出来一下转移方程
if (i-j<=1)
{
f[i][j]=((s[i-1][j]-s[i-1][j-i])%10000+10000)%10000;
} else
{
f[i][j]=s[i-1][j];
}
s[i][j]=s[i][j-1]+f[i][j];
s[i][j]=(s[i][j]%10000+10000)%10000;
f[i][j]=(f[i][j]%10000+10000)%10000;
}
}
printf("%d",f[n][k]);
return 0;
}
```
A了,然后改数据,加极端数据.
极端数据啊,显然可以打表,那就再来两组大数据.
然后n^3的就过不了了