记牛客月赛的小坑: MoonLight的运算问题

怼烎@ 2024-03-17 20:11 6阅读 0赞

#### 文章目录 ####

*   *  题目
     *  本来的解答
     *  正确答案

### 题目 ###

月色哥哥手中有一个数字 x，最初 x=0。给出一个长度为 n 的序列a，月色哥哥会从序列的第一个元素  a 1 a\_1 a1 按顺序看到序列的最后一个元素  a n a\_n an。对于序列的第 i 个元素  a i a\_i ai，月色哥哥可以进行下面的操作之一：

*   x = x ∗ a x=x\*a x=x∗a
 *   x = x + a x=x+a x=x\+a

请求出 x 的最大值，并输出这个最大值除 998244353 的余数。

输入为测试用例组数字, 每组用例第一行为序列长度n, 第二行为n个整数

### 本来的解答 ###

这里采用动态规划的思路:

dp\[i\] 表示对于前 i 个元素,x 的最大值  
通过比较 x \*= a\[i\] 和 x += a\[i\] 的大小,决定下一步的最优操作  
迭代计算 dp 数组,最终 dp\[n\] 即为所求最大 x  
时间复杂度 O(N),空间复杂度 O(N)。

甚至考虑到了int溢出还用了long ， 奶奶的！

dp嘛 很简单

import java.util.Scanner;
    
    public class Main {
        
    
        static final long MOD = 998244353;
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
    
            int numCases = sc.nextInt();
            while (numCases-- > 0) {
        
                int n = sc.nextInt();
                int[] nums = new int[n];
                for (int i = 0; i < n; i++) {
        
                    nums[i] = sc.nextInt();
                }
    
                System.out.println(calculateMaxX(nums));
            }
    
            sc.close();
        }
    
        static long calculateMaxX(int[] nums) {
        
            int n = nums.length;
            long[] dp = new long[n + 1];
            dp[1] = nums[0];
    
            for (int i = 2; i <= n; i++) {
        
                long mul = dp[i-1] * nums[i-1];
                long add = dp[i-1] + nums[i-1];
                dp[i] = Math.max(mul, add);
            }
    
            return dp[n]%MOD;
        }
    
    }

结果死活不能AC  
[https://www.bilibili.com/video/BV1Ag4y1A7J5/?p=4][https_www.bilibili.com_video_BV1Ag4y1A7J5_p_4]题解中说这是经典坑题

因为在x=0或者1时候，肯定是选择加  
大于等于2时肯定选择乘

### 正确答案 ###

import java.util.Scanner;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            int t = in.nextInt();
            while (t-->0) {
        
                int n = in.nextInt();
                long x = 0;
                boolean f = false;
                for (int i = 0; i < n; i++) {
        
                    int a = in.nextInt();
    
                    if(x <= 1 && !f){
        
                        x += a;
                    }else if(a >= 2){
        
                        x *= a;
                    }else{
        
                        x += a;
                    }
                    if (x > 1)
                        f = true;
    
                    x %= 998244353;
    
                }
                System.out.println(x);
            }
        }
    }

[https_www.bilibili.com_video_BV1Ag4y1A7J5_p_4]: https://www.bilibili.com/video/BV1Ag4y1A7J5/?p=4