欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ACM-ICPC 2018 焦作赛区网络预赛 B. Mathematical Curse(dp)

程序员文章站 2022-03-12 15:28:22
...

题目链接:https://nanti.jisuanke.com/t/31711

ACM-ICPC 2018 焦作赛区网络预赛 B. Mathematical Curse(dp)

ACM-ICPC 2018 焦作赛区网络预赛 B. Mathematical Curse(dp)

 

样例输入 
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;
}