考试终于结束了,把当时没有写的补补(太菜了)
奇怪的段
原题链接:< https://www.lanqiao.cn/problems/12112/learning/?contest_id=160 >
这题的思路就是要运用二维dp来遍历一遍,状态方程是:dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + a[i] * p[j],这里有两点要注意的地方,一个是初始化要1ll << 60 的负,大了的话就会错,还有一点,赋值之后要先预处理00的位置为0。当时写这题的时候就剩10多分钟了,而且初始化范围没有弄对……
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <vector>
#include <set>
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define ll long long
#define PII std::pair<int,int>
const ll N = 1e5 + 100;
const ll inf = 1ll << 60;
ll dp[N][230];
void solve(){
ll n,k;
std::cin >> n >> k;
std::vector<ll> op1(n + 1),op2(k + 1);
for(ll i = 1; i <= n; i ++){
std::cin >> op1[i];
}
for(ll i = 1; i <= k; i ++) std::cin >> op2[i];
for(ll i = 0; i <= n; i ++){
for(ll j = 0; j <= k; j ++){
dp[i][j] = -inf;
}
}
dp[0][0] = 0;
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= k; j ++){
dp[i][j] = std::max(dp[i - 1][j],dp[i - 1][j - 1]) + op1[i] * op2[j];
}
}
std::cout << dp[n][k] << "\n";
return;
}
int main(){
IOS
ll t = 1;
// std::cin >> t;
while(t --)
solve();
return 0;
}
小蓝的反击
最后一题不知道用什么算法实现呜呜呜