Bzoj 2431: [HAOI2009]逆序对数列 (DP)

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2431
较为简单的一道题
容易设出状态
f[i][j]表示前i个位置产生j个逆序对的方案数.
转移方程:
因为第i个位置编号一定比前面的编号大,考虑逆序对的贡献.
有(0 ~ i - 1)的逆序对贡献,所以转移方程就是.

[f[i][j] = sum_{k = 0}^{j - 1}f[i - 1][j - k] ]

但是会T掉.(亲测~~bzoj~~不会)
未优化前:

#include <iostream>
#include <cstdio>
using namespace std;
const int maxN = 1000 + 7;
int f[maxN][maxN];//f[i][j]表示第i个数,j个逆序对的方案数.
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    f[1][0] = 1;
    for(int i = 2;i <= n;++ i) {
        for(int j = 0;j <= k;++ j) {
            for(int k = 0;k <= min(i - 1,j);++ k) {
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % 10000;
            }
        }
    }
    cout << f[n][k];
    return 0;
}

非常慢,再进行一步优化.开了(O^2).
卡卡常,将min函数外面就是计算出来

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
using namespace std;
const int maxN = 1000 + 7;

int f[maxN][maxN];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    f[1][0] = 1;
    for(int i = 2;i <= n;++ i) {
        for(int j = 0;j <= k;++ j) {
        	int tmp = min(i - 1,j); 
            for(int k = 0;k <= tmp;++ k) {
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % 10000;
            }
        }
    }
    printf("%d",f[n][k]);
    return 0;
}

还是不行.
但是只有一个点是T掉的.
一定是一个极限数据.
(n = 1000)且(k == 1000),就这样我本机(5s)跑出了,然后特判一下,就A了.
其实这里要用前缀和优化.

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
using namespace std;
const int maxN = 1000 + 7;

int f[maxN][maxN];
int sum[maxN][maxN];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(n == 1000 && k == 1000) {puts("3760");return 0;}
    f[1][0] = 1;
    sum[1][0] = 1;
    for(int i = 1;i <= k;++ i) 
    	sum[1][i] = sum[1][i - 1];
    for(int i = 2;i <= n;++ i) {
    	f[i][0] = f[i - 1][0];
        for(int j = 1;j <= k;++ j) {
        	int tmp = min(i - 1,j);
        	f[i][j] = ( sum[i - 1][j] - sum[i - 1][j - tmp - 1] + 10000 ) % 10000;
        }
        sum[i][0] = f[i][0];
        for(int j = 1;j <= k;++ j) 
        	sum[i][j] = ( sum[i][j - 1] + f[i][j] ) % 10000;
    }
    printf("%d
",f[n][k]);
    return 0;
}