|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
最值序列
说明
给一个长度为n的序列a_i ,一开始你有一个数A = 0,每次可以从序列中选一个数b,令A = A + b或者A = A * b,每个数都要使用一次,加的次数要和乘的次数近可能相近,要求最大化A,输出A对998244353取模的值
输入格式
第一行为一个整数n,表示序列的长度
第二行为n个整数a_i
描述这个序列,
2≤n≤10^3,1<a_i≤10^9
输出格式
一个非负整数,表示A的最大值对998244353取模的值
样例
输入数据 1
4
3 3 2 4
输出数据 1
60
提示
(2+3)×3×4=60
题目要求给定一个长度为n的序列a_i,每次可以从序列中选择一个数b,使得A = A + b或者A = A * b,最终要求最大化A对998244353取模的值。
这个问题可以使用动态规划来解决。我们定义一个二维数组dp,其中dp [j]表示选择前i个数使用了j次加法操作时的最大值。状态转移方程如下:
dp[j] = max(dp[i-1][j-1]*a, dp[i-1][j]+a)
其中,dp[i-1][j-1]*a表示选择第i个数乘法操作,dp[i-1][j]+a表示选择第i个数加法操作。
最终结果就是dp[n][n/2],即选择前n个数使用n/2次加法操作时的最大值。
下面是完整的C++代码实现:
- #include <iostream>
- #include <vector>
- using namespace std;
- const int MOD = 998244353;
- int main() {
- int n;
- cin >> n;
- vector<int> a(n+1);
- for (int i = 1; i <= n; ++i) {
- cin >> a[i];
- }
- vector<vector<int>> dp(n+1, vector<int>(n/2+1));
- dp[0][0] = 0;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= n/2; ++j) {
- dp[i][j] = max(dp[i-1][j-1]*a[i], dp[i-1][j]+a[i]);
- dp[i][j] %= MOD;
- }
- }
- cout << dp[n][n/2] << endl;
- return 0;
- }
复制代码
希望能帮到你!如果还有其他问题,尽管问。
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
|
|