这一题比赛时纠结了好久才发现()()()...的形式是最优的，因为这样除了配对的括号之外，两个()之间可以有更多的组合。而((()))就不及前一种形式。
组合数就是单个配对的括号数,e.g., () +任意两个()及其中间的配对括号的数目, e.g., ()()...()()。我开始还以为要用组合数计算，后来发现就是(n-1)n/2
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include<ctype.h> #include<map> #include<time.h> #include<set> #include<bitset> #include<sstream> using namespace std; //Google APAC2017 Round B Problem A. Sherlock and Parentheses const int maxn=100010; int T; long long L; long long R; long long ans; long long comb[maxn][maxn]; void init() { memset(comb,0,sizeof(comb)); comb[0][0]=1; for(int i=0;i<maxn;i++) { comb[i][0]=1; comb[i][i]=1; } for(int i=1;i<maxn;i++) { for(int j=1;j<2;j++) { comb[i][j]=comb[i-1][j]+comb[i-1][j-1]; //cout<<i<<" "<<j<<" "<<comb[i][j]<<endl; } } } int main() { freopen("A-large.in","r",stdin); freopen("B-small-practice.out","w",stdout); scanf("%d",&T); // init(); for(int ca=1;ca<=T;ca++) { scanf("%lld %lld",&L,&R); ans=0; long long tmp=min(L,R); ans=tmp+tmp*(tmp-1)/2; printf("Case #%d: %lld\n",ca,ans); } return 0; }
