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);
        }
    }
AI 代码解读
iamzfh
+关注
目录
打赏
0
7
7
0
48
分享
相关文章
codeforces 285C - Building Permutation
题目大意是有一个含n个数的数组,你可以通过+1或者-1的操作使得其中的数是1--n中的数,且没有重复的数。 既然是这样的题意,那么我就应该把原数组中的数尽量往他最接近1--n中的位置放,然后求差绝对值之和,但有多个数,怎么使他们和最小,这样就要对其进行排序了,直接按大小给它们安排好位置,然后计算。
45 0
|
4月前
|
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
105 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
B. Fake Plastic Trees(贪心+dp)
B. Fake Plastic Trees(贪心+dp)
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
87 0
LeetCode 329. Longest Increasing Path in a Matrix
LeetCode 334. Increasing Triplet Subsequence
给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。 数学表达式如下: 如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1, 使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
104 0
LeetCode 334. Increasing Triplet Subsequence
【LeetCode】Increasing Triplet Subsequence(334)
  Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
111 0
成功解决coordinate_descent.py:491: ConvergenceWarning: Objective did not converge. You might want to inc
成功解决coordinate_descent.py:491: ConvergenceWarning: Objective did not converge. You might want to inc
Matrix Factorization
Matrix Factorization ①linearNetwork Hypothesis 机器学习的作用就是要从一堆数据中学习到学习到某种能力,然后用这种skill来预测未来的结果。
1071 0

热门文章

最新文章