ACM-ICPC 2018 焦作赛区网络预赛 B. Mathematical Curse(dp)
程序员文章站
2022-03-12 15:28:22
...
题目链接:https://nanti.jisuanke.com/t/31711
样例输入
3
2 1 5
2 3
/
3 2 1
1 2 3
++
4 4 5
1 2 3 4
+-*/
样例输出
2
6
3
题意: n个数字,m个运算符(+-*/),从n个数字中选择m个数字,按原数组顺序与k进行运算,使得最后结果最大
思路:dp[i][j]表示取到i这个数字,用了j个操作符的最大值,而f[i][j]表示最小值。
dp[i][j]等于dp[i-1][j](当前i数字不取)dp[i-1][j-1] op a[i](上一个状态最大值,当前i数字取)以及f[i-1][j-1] op a[i](上一个状态最小值,当前i数字取)中的最大值
f[i][j]同理,取最小值,最后dp[n][m]就是答案。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define maxn 300005
using namespace std;
typedef long long ll;
const ll inf=1e18;
ll solve(ll x,char op,ll y){
if(op=='+')return x+y;
if(op=='-')return x-y;
if(op=='*')return x*y;
if(op=='/')return x/y;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
ll a[1100],k;
char s[10];
scanf("%d%d",&n,&m);
scanf("%lld",&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
scanf("%s",s+1);
ll dp[1100][10];
ll f[1100][10];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=-inf;
f[i][j]=inf;
}
}
for(int i=0;i<=n;i++){
dp[i][0]=k;
f[i][0]=k;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i<=m&&j>i)break;
dp[i][j]=max(solve(dp[i-1][j-1],s[j],a[i]),dp[i-1][j]);
dp[i][j]=max(solve(f[i-1][j-1],s[j],a[i]),dp[i][j]);
f[i][j]=min(solve(f[i-1][j-1],s[j],a[i]),f[i-1][j]);
f[i][j]=min(solve(dp[i-1][j-1],s[j],a[i]),f[i][j]);
}
}
printf("%lld\n",dp[n][m]);
}
return 0;
}
上一篇: 1 基于图灵机器人的对话
下一篇: 教你如何制作VB的P-Code调试器
推荐阅读
-
ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze(队列优化的dijkstra,dp)
-
ACM-ICPC 2018 焦作赛区网络预赛 L Poor God Water 线性模板题 or 矩阵快速幂推导
-
ACM-ICPC 2018 徐州赛区网络预赛-B.BE, GE or NE-对抗博弈dp
-
ACM-ICPC 2018 徐州赛区网络预赛 B. BE, GE or NE(博弈,记忆化搜索)
-
ACM-ICPC 2018 焦作赛区网络预赛 K. Transport Ship (多重背包+方案记录)
-
ACM-ICPC 2018 焦作赛区网络预赛 G. Give Candies(大数幂,欧拉降幂)
-
ACM-ICPC 2018 焦作赛区网络预赛 A. Magic Mirror(水)
-
费马小定理+快速幂:ACM-ICPC 2018 焦作赛区网络预赛 G. Give Candies
-
L. Poor God Water [ ACM-ICPC 2018 焦作赛区网络预赛 ]
-
ACM-ICPC 2018 焦作赛区网络预赛 Poor God Water(递推+构造矩阵)