SP64 PERMUT1 - Permutations 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 还没有评论
作者: shame_djj 更新时间: 2019-11-05 21:07  在Ta的博客查看 举报    1  

莫名 RE 好几次,后来发现原来是读入 long long 忘记改成了 %lld

原题链接【PERMUT1 - Permutations】

楼下的 dp 时间复杂度是 O (n3) 的,但是他的 dp 显然是可以优化的

我们观察楼下的 dp

    dp[1][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            for(int l=0;l<i;l++){
                if(j>=l)
                    dp[i][j]+=dp[i-1][j-l];

第三重循环,其实是对于一些特殊限定地方的值求了一个和

而对于这样的 dp ,有一种常见的优化,叫作前缀和优化

预处理前缀和,或者边向前走,边处理前缀和,是前缀和优化 dp 的两种基本形式

我使用的是第二种形式

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define int long long

using namespace std;

int dp[1010][1010];

signed main () {
    dp[1][0] = 1;
    for (register int i = 2; i <= 1000; i ++) {
        int sum = 0;
        for (register int j = 0; j <= 1000; j ++) {
            sum += dp[i - 1][j];
            dp[i][j] = sum;
            if (j >= i - 1)
                sum -= dp[i - 1][j - i + 1];
        }
    }
    int T, n, k; scanf ("%lld", &T);
    for (; T; T --) {
        scanf ("%lld %lld", &n, &k);
        printf ("%lld\n", dp[n][k]);
    }
    return 0;
}

经过前缀和优化后,我们的 dp 的时间复杂度将为了 O(n2)

可过楼上所说的那道 HA 省选题 [HAOI2009]逆序对数列

离 CSP-S 还有不到十天,祝大家 rp ++

也希望自己能更努力一些,加油

评论

  • 17shou_VIP
    dalao你tql!!
  • 17shou_VIP
    %%%
  • Billy●Herrington
    dalao你tql!!
  • Billy●Herrington
    %%%
  • xiaduowen
    李剑儒你你tql!!
  • 陈楷文
    顶楼上
  • 牟星宇
    其实这代码有问题我们考了试我去测没ac
作者: 17shou_VIP  更新时间: 2018-12-08 22:07  在Ta的博客查看 举报    1  

我会告诉你这是三倍经验题吗。。。

做完这道你可以去做P1521 求逆序对P2513 [HAOI2009]逆序对数列

但是我并不确定我的代码在P2513不会TLE


在这道题中,你会发现你逆序对的个数只和相对大小有关!!

然后就可以建立DP模型:dp[i][j]表示i个不同的数的所有排列中,逆序对数量为j的排列个数。初始边界为dp[1][0]=1。

关于dp方程:当有i-1个数时,有j-1个逆序对时,添加第i个数,必有一个位置刚好使逆序对数+1,即可转移到dp[i][j]。同理j-2,j-3……j-(i-1),因为只有i-1个数,所以最多到i-1,当然也可能不增加逆序对。

Code:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,w;
int dp[1001][1001];
int main(){
    scanf("%d",&w);
    while (w--){
        memset(dp,0,sizeof (dp));
        scanf("%d%d",&n,&k);
        dp[1][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                for(int l=0;l<i;l++){
                if(j>=l)
                    dp[i][j]+=dp[i-1][j-l];
                }
            }
        }
        printf("%d\n",dp[n][k]);
    }
    return 0;
}

本蒟蒻第一篇题解。有什么不好的地方可以私信留言哈~~~

^_^

反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。