2078D. Scammy Game Ad · znzryb
## 思路讲解
当发现裸的暴搜和状压不行了，这个时候就要开始想贪心了。（我怎么感觉这道题目的数据范围在误导我那）
参考以下题解，竟然是个贪心，佛了。
> 【Codeforces Round 1008 (Div. 2) 题目讲解 ABCDEF (CF2078)】 【精准空降到 19:54】 [https://www.bilibili.com/video/BV13WQVYxEPC/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1194](https://www.bilibili.com/video/BV13WQVYxEPC/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1194)
主要思路就是可以通过贪心，+和x相比，肯定x划算，x2和x3相比，肯定x3划算，然后就可以了。注意是一段一段，因为每次增加的可以重新分配。每次增加的多了，经过重新分配，总量也就多了。
## AC代码
[https://codeforces.com/contest/2078/submission/310089733](https://codeforces.com/contest/2078/submission/310089733)
```cpp
// Problem: D. Scammy Game Ad
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/contest/2078/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,4> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T;
// ll sum1[MAXN],mul1[MAXN],sum2[MAXN],mul2[MAXN];
struct OPER{
char op1,op2;ll num1,num2;
}oper[MAXN];
inline void solve(){
cin>>N;
// sum1[0]=0;
// mul1[0]=1;
// sum2[0]=0;
// mul2[0]=1;
for(int i=1;i<=N;++i){
cin>>oper[i].op1>>oper[i].num1>>oper[i].op2>>oper[i].num2;
}
ll lans=1,rans=1;
for(int i=1;i<=N;++i){
bool goLeft=true;
for(int j=i+1;j<=N;++j){
char op1=oper[j].op1,op2=oper[j].op2;
ll num1=oper[j].num1,num2=oper[j].num2;
if(op1=='+' && op2=='x'){
goLeft=false;
break;
}else if(op1=='x' && op2=='x' && num2>num1){
goLeft=false;
break;
}else if(op1=='x' && op2=='+'){
goLeft=true;
break;
}else if(op1=='x' && op2=='x' && num2<num1){
goLeft=true;
break;
}
}
char op1=oper[i].op1,op2=oper[i].op2;
ll num1=oper[i].num1,num2=oper[i].num2;
ll t1=0,t2=0;
if(op1=='x') t1=num1*lans-lans;
else t1=num1;
if(op2=='x') t2=num2*rans-rans;
else t2=num2;
if(goLeft){
lans+=(t1+t2);
}else{
rans+=(t1+t2);
}
// #ifdef LOCAL
// cerr << lans<<" "<<rans << '\n';
// #endif
}
cout<<lans+rans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
AC
https://codeforces.com/contest/2078/submission/310089733
*/
```
## 心路历程（WA，TLE，MLE……）
注意，不仅遇到goRight的要停，goLeft的也要停。
这个算法其实问题在于虽然说后面乘数越多，你这个人的贡献就越大。但是问题在于如果一个人可以在比较早的时候变为多个人，然后再反哺回去，可能贡献更大？（如样例的第二个测试数据）
```cpp
// Problem: D. Scammy Game Ad
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/contest/2078/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,4> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
ll sum1[MAXN],mul1[MAXN],sum2[MAXN],mul2[MAXN];
struct OPER{
char op1,op2;ll num1,num2;
}oper[MAXN];
inline void solve(){
cin>>N;
// sum1[0]=0;
// mul1[0]=1;
// sum2[0]=0;
// mul2[0]=1;
for(int i=1;i<=N;++i){
cin>>oper[i].op1>>oper[i].num1>>oper[i].op2>>oper[i].num2;
}
mul1[N+1]=1;
mul2[N+1]=1;
for(int i=N;i>=1;--i){
if(oper[i].op1=='x'){
mul1[i]=mul1[i+1]*oper[i].num1;
}else{
mul1[i]=mul1[i+1];
}
if(oper[i].op2=='x'){
mul2[i]=mul2[i+1]*oper[i].num2;
}else{
mul2[i]=mul2[i+1];
}
}
ll lans=1,rans=1;
for(int i=1;i<=N;++i){
ll num1=oper[i].num1,num2=oper[i].num2;
ll lres=0,rres=0; // 本次l和r需要增加的次数
if(oper[i].op1=='x'){
ll t=lans*num1-lans;
if(mul1[i+1]>=mul2[i+1]){
lres+=t;
}else{
rres+=t;
}
}else{
ll t=num1;
if(mul1[i+1]>=mul2[i+1]){
lres+=t;
}else{
rres+=t;
}
}
if(oper[i].op2=='x'){
ll t=rans*num2-rans;
if(mul1[i+1]>=mul2[i+1]){
lres+=t;
}else{
rres+=t;
}
}else{
ll t=num2;
if(mul1[i+1]>=mul2[i+1]){
lres+=t;
}else{
rres+=t;
}
}
lans+=lres;
rans+=rres;
}
cout<<lans+rans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
*/
```