2012 East Central Regional Contest Gym100642E

本文主要是介绍2012 East Central Regional Contest Gym100642E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

爆搜

  1 #include<bits/stdc++.h>
  2 #define maxn 20
  3 #define LL long long 
  4 #define INF 0x7fffffff
  5 using namespace std;
  6 int seg[maxn],n,r1,r2;
  7 char op[maxn],o[maxn];
  8 LL cal(LL x,LL y,char opt){
  9     if(opt=='*') return x*y;
 10     else if(opt=='+') return x+y;
 11     else if(opt=='-') return x-y;
 12 }
 13 LL dfs1(LL *a,int len1,char *s,int len2,int p){
 14     LL xx;
 15     if(len1==3){
 16         if(p==1){
 17             xx=max(cal(cal(a[1],a[2],s[1]),a[3],s[2]),cal(a[1],cal(a[2],a[3],s[2]),s[1]));
 18             return xx;
 19         }
 20         else{
 21             xx=min(cal(cal(a[1],a[2],s[1]),a[3],s[2]),cal(a[1],cal(a[2],a[3],s[2]),s[1]));
 22             return xx;
 23         }
 24     }
 25     if(len1==2){
 26         return cal(a[1],a[2],s[1]);
 27     }
 28     if(len1==1){
 29         return a[1];
 30     }
 31     LL tem[maxn],t;
 32     char o[maxn];
 33     if(p==1) t=-INF;
 34     else t=INF;
 35     for(int i=1;i<len1;i++){
 36         for(int j=1;j<=i-1;j++) tem[j]=a[j];
 37             tem[i]=cal(a[i],a[i+1],s[i]);    
 38         for(int j=i+1;j<=len1-1;j++) tem[j]=a[j+1];
 39         for(int j=1;j<=i-1;j++) o[j]=s[j];
 40         for(int j=i+1;j<=len2;j++) o[j-1]=s[j];
 41         xx=dfs1(tem,len1-1,o,len2-1,p^1);
 42         if(p==1){
 43             t=max(t,xx);
 44         }
 45         else 
 46             t=min(t,xx);
 47     }
 48     return t;
 49 }
 50 int main(){
 51 //    freopen("txt.out","w",stdout);
 52     int T;
 53     cin>>T;
 54     int flag=0,tot=0;
 55     LL tem[maxn];
 56     LL res,l1,l2,ans;
 57     while(T--){
 58         cin>>n;
 59         n++;
 60         r1=-INF,r2=INF;
 61         for(int i=1;i<=n-1;i++){
 62             scanf("%d",&seg[i]);
 63             cin>>op[i];
 64         }
 65         cin>>seg[n];
 66     for(int i=1;i<n;i++){
 67         for(int j=1;j<=i-1;j++) tem[j]=seg[j];
 68             tem[i]=cal(seg[i],seg[i+1],op[i]);    
 69         for(int j=i+1;j<=n-1;j++) tem[j]=seg[j+1];
 70         for(int j=1;j<=i-1;j++) o[j]=op[j];
 71         for(int j=i+1;j<=n-1;j++) o[j-1]=op[j];
 72         res=dfs1(tem,n-1,o,n-2,0);
 73         if(r1<res){
 74             r1=res;
 75             l1=i;
 76         }
 77     }
 78     cout<<"Case "<<++tot<<":"<<endl;
 79     cout<<"Player 1 "<<"("<<seg[l1]<<op[l1]<<seg[l1+1]<<") leads to "<<r1<<endl;
 80     for(int i=1;i<n;i++){
 81         for(int j=1;j<=i-1;j++) tem[j]=seg[j];
 82             tem[i]=cal(seg[i],seg[i+1],op[i]);    
 83         for(int j=i+1;j<=n-1;j++) tem[j]=seg[j+1];
 84         for(int j=1;j<=i-1;j++) o[j]=op[j];
 85         for(int j=i+1;j<=n-1;j++) o[j-1]=op[j];
 86         res=dfs1(tem,n-1,o,n-2,1);
 87         if(r2>res){
 88             r2=res;
 89             l2=i;
 90         }
 91     }
 92     cout<<"Player 2 "<<"("<<seg[l2]<<op[l2]<<seg[l2+1]<<") leads to "<<r2<<endl;
 93     if(r1>-r2) flag=1;
 94     else if(r1<-r2) flag=-1;
 95     else flag=0;
 96     if(flag==1) cout<<"Player 1 wins"<<endl;
 97     else if(flag==-1) cout<<"Player 2 wins"<<endl;
 98     else cout<<"Tie"<<endl;
 99     }
100     return 0;
101 }