C++14(g++5.4) 解法, 执行用时: 320ms, 内存消耗: 55240K, 提交时间: 2019-12-11 20:04:16
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
typedef long long ll;
ll a[maxn], b[maxn], dp[maxn][5];
int main()
{
ll n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &a[i], &b[i]);
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i - 1][0] + b[i - 1] * a[i];
dp[i][1] = dp[i - 1][0] + k * b[i - 1] * a[i];
dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + k * k * b[i - 1] * a[i];
dp[i][3] = max(dp[i - 1][2] + k * b[i - 1] * a[i], dp[i - 1][3] + b[i - 1] * a[i]);
}
cout << max(dp[n][0], max(dp[n][2], dp[n][3]));
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 387ms, 内存消耗: 55180K, 提交时间: 2023-03-13 21:01:12
#include<bits/stdc++.h>
using namespace std;
long long int a[1000005],b[1000005],dp[1000005][5];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
for(int i=2;i<=n;i++)
{
dp[i][0]=dp[i-1][0]+b[i-1]*a[i];
dp[i][1]=dp[i-1][0]+k*b[i-1]*a[i];
dp[i][2]=max(dp[i-1][1],dp[i-1][2])+k*k*b[i-1]*a[i];
dp[i][4]=max(dp[i-1][2]+k*b[i-1]*a[i],dp[i-1][4]+b[i-1]*a[i]);
}
cout<<max(dp[n][0],max(dp[n][2],dp[n][4]));
}
C++11(clang++ 3.9) 解法, 执行用时: 785ms, 内存消耗: 63768K, 提交时间: 2020-02-25 14:49:20
#include<bits/stdc++.h>
using namespace std;
long long int a[1000005],b[1000005],dp[1000005][5];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
for(int i=2;i<=n;i++)
{
dp[i][0]=dp[i-1][0]+b[i-1]*a[i];
dp[i][1]=dp[i-1][0]+k*b[i-1]*a[i];
dp[i][2]=max(dp[i-1][1],dp[i-1][2])+k*k*b[i-1]*a[i];
dp[i][4]=max(dp[i-1][2]+k*b[i-1]*a[i],dp[i-1][4]+b[i-1]*a[i]);
}
cout<<max(dp[n][0],max(dp[n][2],dp[n][4]));
}
)
`,而这些宝石是可以融合的，并且在融合的过程中会释放出大量的能量(只有相邻的宝石可以融合)。融合规则是：存在两个相邻的宝石`%E5%92%8C(a_2%2Cb_2))
`,如果融合这两个宝石,宝石就会变成`)
`并释放出`
`的能量,现在要找到融合成一块宝石并且产生能量最大的方案。`
`