Gym 102394 I. Interesting Permutation(DP)

简介: 【7月更文挑战第3天】

链接

题意:

给你一个数字n,然后有一个长度为n的数列,这个数列的第 i 项值时某个数列的前 i 项的最大值减去最小值的到的结果,问你用着n个数字能构造出来多少种长度为n的数列。

分析:

首先我们考虑一下一定没有答案的方案:

  • 如果开头不是0,或者结尾不是n-1一定没有答案
  • 如果整个序列不是单调递增一定没有答案
  • 如果差值小于序列长度-1,一定没有答案(长度为x,差值最小这x个数分别是1,2..x,这样差值为x-1所以差值不会小于序列长度-1)

然后我们分析:我们刚拿到这个问题,不知道如何解决,那么我们得找到一个突破口,这个突破口最最后(n-1)的地方,

我们看,当出现n-1时,该位置,一定放了(1或者n)这点是毋容置疑的。

然后我们该位置有两种放法(假设放了1)那么后面等于(n-1)的先空出来计数有num个空,

再往前看,如果前一个数为(n-2)那么我们肯定就是可以放(2或者n)这样该能使的满足差值为(n-2),(假设我们放了2)

然后跟上面一样,在往前看如果前一个数为(n-4),那么我们想这个位置可以放的数(4或者n)如果放了4,但是我们还有3,他肯定在这个位置之后放, 那就用到我们前面记录的num个空了,在这num个空中选一个放4即可。(放n同理也要把3放进空中)。

那么我们就得出:

int _;
    scanf("%d", &_);
    while (_--)
    {
   
        scanf("%lld", &n);
        ll flag = 1;
        for(int i = 1; i <= n; i++)
        {
   
            scanf("%lld", &a[i]);
            if(i == 1)
            {
   
                if(a[i] != 0) flag = 0;///不是0开头一定没有答案
            }
            else
            {
   
                if(a[i] < a[i - 1]) flag = 0;///不单调递增 一定没有答案
                if(a[i] < i - 1) flag = 0;///这个是差值小于数量一定没有答案
            }
        }

        if(a[n] != n - 1) flag = 0;//最终差值不为n-1一定没有答案
        if(flag == 0) puts("0");//没有答案输出0
        else
        {
   
            ll ans = 1;
            ll num = 0;
            for(int i = n; i > 1; i--)
            {
   
                int j = i;
                while(j > 1 && a[j] == a[i]) j--, num++;/// 相同的数量
                num--;
                for(int k = 1; k <= a[i] - a[j] - 1; k++)
                {
   
                    ans = ans * num  % MOD;/// 选取最小的数 有num位置可以选择
                    num--;
                }            
                ans = ans * 2 % MOD;/// 两种选择
                i = j + 1;///转移到与其不同的敌方。
            }
            printf("%lld\n", ans);
        }
    }
目录
相关文章
codeforces 285C - Building Permutation
题目大意是有一个含n个数的数组,你可以通过+1或者-1的操作使得其中的数是1--n中的数,且没有重复的数。 既然是这样的题意,那么我就应该把原数组中的数尽量往他最接近1--n中的位置放,然后求差绝对值之和,但有多个数,怎么使他们和最小,这样就要对其进行排序了,直接按大小给它们安排好位置,然后计算。
32 0
|
6月前
|
vr&ar C++
B. Fake Plastic Trees(贪心+dp)
B. Fake Plastic Trees(贪心+dp)
|
存储
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
69 0
LeetCode 329. Longest Increasing Path in a Matrix
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
115 0
Leetcode-Easy 461.Hamming Distance
Leetcode-Easy 461.Hamming Distance
108 0
Leetcode-Easy 461.Hamming Distance
Leetcode-Easy 867.Transpose Matrix
Leetcode-Easy 867.Transpose Matrix
90 0
Gym 100952H&&2015 HIAST Collegiate Programming Contest H. Special Palindrome【dp预处理+矩阵快速幂/打表解法】
H. Special Palindrome time limit per test:1 second memory limit per test:64 megabytes input:standard input output:standard o...
916 0
Gym 100952D&&2015 HIAST Collegiate Programming Contest D. Time to go back【杨辉三角预处理,组合数,dp】
D. Time to go back time limit per test:1 second memory limit per test:256 megabytes input:standard input output:standard output ...
1138 0