Description
【故事背景】
JYY很喜欢打保龄球，虽然技术不高，但是还是总想着的高分。这里JYY
将向你介绍他所参加的特殊保龄球比赛的规则，然后请你帮他得到尽量多的分数。
【问题描述】
一场保龄球比赛一共有N个轮次，每一轮都会有10个木瓶放置在木板道的
另一端。每一轮中，选手都有两次投球的机会来尝试击倒全部的10个木瓶。对于每一次投球机会，选手投球的得分等于这一次投球所击倒的木瓶数量。选手每一轮的得分是他两次机会击倒全部木瓶的数量。
对于每一个轮次，有如下三种情况：
1、“全中”：如果选手第一次尝试就击倒了全部10个木瓶，那么这一轮就称
为“全中”。在一个“全中”轮中，由于所有木瓶在第一次尝试中都已经被击倒，所以选手不需要再进行第二次投球尝试。同时，在计算总分时，选手在下一轮的得分将会被乘2计入总分。
2、“补中”：如果选手使用两次尝试击倒了10个木瓶，那么这一轮就称为“补中”。同时，在计算总分时，选手在下一轮中的第一次尝试的得分将会被乘以2计入总分。
3、“失误”：如果选手未能通过两次尝试击倒全部的木瓶，那么这一轮就被称为“失误”。同时，在计算总分时，选手在下一轮的得分会被计入总分，没有分数被翻倍。此外，如果第N轮是“全中”，那么选手可以进行一次附加轮：也就是，如果第N轮是“全中”，那么选手将一共进行N+1轮比赛。显然，在这种情况下，第N+1轮的分数一定会被加倍。
附加轮的规则只执行一次。也就是说，即使第N+1轮选手又打出了“全中”，也不会进行第N+2轮比赛。因而，附加轮的成绩不会使得其他轮的分数翻番。最后，选手的总得分就是附加轮规则执行过，并且分数按上述规则加倍后的每一轮分数之和。
JYY刚刚进行了一场N个轮次的保龄球比赛，但是，JYY非常不满意他的
得分。JYY想出了一个办法：他可以把记分表上，他所打出的所有轮次的顺序重新排列，这样重新排列之后，由于翻倍规则的存在，JYY就可以得到更高的分数了！当然了，JYY不希望做的太假，他希望保证重新排列之后，所需要进行的轮数和重排前所进行的轮数是一致的：比如如果重排前JYY在第N轮打出了“全中”，那么重排之后，第N轮还得是“全中”以保证比赛一共进行N+1轮；同样的，如果JYY第N轮没有打出“全中”，那么重排过后第N轮也不能是全中。请你帮助JYY计算一下，他可以得到的最高的分数。
Input
第一行包含一个整数N，表示保龄球比赛所需要进行的轮数。
接下来包含N或者N+1行，第i行包含两个非负整数Xi和Yi，表示JYY在
这一轮两次投球尝试所得到的分数，Xi表示第一次尝试，Yi表示第二次尝试。
我们用表示一个“全中”轮。输入数据保证。
读入数据存在N+1行，当且仅当Xn=10且Yn=10。
Output
输出一行一个整数，表示JYY最大可能得到的分数。
Sample Input
2
5 2
10 0
3 7
5 2
10 0
3 7
Sample Output
44
HINT
【样例说明】
按照输入顺序，JYY将得到37分。
最佳方案是将3个轮次排列成如下顺序：
3 7
10 0
5 2
N<=50
JSOI2014第二轮D2T2
写了400多行= =
我是分有无附加轮分两种情况讨论。然后分补中多还是全中多又各分两种
我们知道要最大肯定是 补中 全中 补中 全中 这样类似的排列。
然后就可以贪心了！
然后我们再可以枚举每两个位置进行交换来调整答案。
最后一个点一开始死活都小了1了= =然后调整的部分就改成了任意两个位置都枚举
反正n就50不是= =随便做
丢下代码吧。。这题我觉得看代码还不如自己考虑。。
【等到以后，这题一定是A掉的最值得纪念的题之一】
#include<cstdio>
#include<algorithm>
using namespace std;
struct score
{
int x,y;
int s;
}a[10001],b[10001],c[10001],d[10001],ax[10001],tt[10001];
inline bool cmp1(score x,score y)
{
if(x.s>y.s)
return true;
if(x.s==y.s&&x.x>y.x)
return true;
return false;
}
inline bool cmp2(score x,score y)
{
if(x.x>y.x)
return true;
return false;
}
int main()
{
// freopen("bowling.in","r",stdin);
// freopen("bowling.out","w",stdout);
int n;
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].s=a[i].x+a[i].y;
}
if(a[n].x!=10)
{
sort(a+1,a+1+n,cmp1);
int x1=0,x2=0,xt=n+1,xx1=0,xx2=0;
for(i=1;i<=n;i++)
{
if(a[i].x==10)
{
x1++;
b[x1]=a[i];
}
else if(a[i].s==10)
{
x2++;
c[x2]=a[i];
}
else
{
xt=i;
break;
}
}
int x3=0;
for(i=xt;i<=n;i++)
{
x3++;
d[x3]=a[i];
}
xx1=x1;
xx2=x2;
int ans=0;
int as=0;
if(x2>0)
{
as++;
ax[as]=c[x2];
x2--;
ans+=10;
//ax[as]=a[xt-(xx2-x2)];
}
while(x2>0&&x1>0)
{
as++;
ax[as].x=10;
ax[as].y=0;
ax[as].s=10;
as++;
//ax[as]=a[xt-(xx2-x2)];
ax[as]=c[x2];
x1--;
x2--;
ans+=40;
}
if(x2>0)
{
sort(d+1,d+1+x3,cmp2);
//sort(c+1,c+1+x2,cmp2);
int d2=1,d2r=x2,d3=1,d3r=x3;
bool flag=true;
while(d2r-d2+1>0&&d3r-d3+1>0)
{
if(flag)
{
if(c[d2].x>d[d3].x||d3r-d3+1==1)
{
as++;
ax[as]=c[d2];
ans+=(c[d2].x*2+c[d2].y);
d2++;
}
else
{
as++;
ax[as]=d[d3];
ans+=(d[d3].x*2+d[d3].y);
d3++;
flag=false;
}
}
else
{
as++;
ax[as]=c[d2r];
ans+=(c[d2r].x+c[d2r].y);
d2r--;
flag=true;
}
}
if(d2r-d2+1>0)
{
if(flag)
{
as++;
ax[as]=c[d2];
ans+=(c[d2].x*2+c[d2].y);
d2++;
}
while(d2r-d2+1>0)
{
as++;
ax[as]=c[d2];
ans+=(c[d2].x+c[d2].y);
d2++;
}
}
else if(d3r-d3+1>0)
{
if(flag)
{
as++;
ax[as]=d[d3];
ans+=(d[d3].x*2+d[d3].y);
d3++;
flag=false;
}
while(d3r-d3+1>0)
{
as++;
ax[as]=d[d3];
ans+=(d[d3].x+d[d3].y);
d3++;
}
}
int ansx=ans;
int j;
for(i=as;i>=1;i--)
if(ax[i].s==10)
break;
int tx=i;
for(i=1;i<=as;i++)
{
if(ax[i].x==10)
{
score t=ax[i];
ax[i]=ax[tx];
ax[tx]=t;
ans=0;
bool flag1=false,flag2=false;
for(j=1;j<=as;j++)
{
if(flag1)
ans+=(ax[j].s*2);
else if(flag2)
ans+=(ax[j].x*2+ax[j].y);
else
ans+=(ax[j].x+ax[j].y);
flag1=false;
flag2=false;
if(ax[j].x==10)
flag1=true;
else if(ax[j].s==10)
flag2=true;
}
ansx=max(ansx,ans);
t=ax[i];
ax[i]=ax[tx];
ax[tx]=t;
}
}
printf("%d\n",ansx);
}
else if(x1>0)
{
if(xx2==0)
ans-=10;
while(x1>0)
{
ans+=20;
x1--;
}
ans+=(a[xt].s*2);
for(i=xt+1;i<=n;i++)
ans+=a[xt].s;
printf("%d\n",ans);
}
}
else
{
for(i=1;i<=n;i++)
tt[i]=a[i];
scanf("%d%d",&tt[n+1].x,&tt[n+1].y);
tt[n+1].s=tt[n+1].x+tt[n+1].y;
int j,k;
int xx;
int ansx=0;
for(k=1;k<=n+1;k++)
{
xx=0;
for(j=1;j<=n+1;j++)
{
if(j!=k)
{
xx++;
a[xx]=tt[j];
}
}
/* printf("\n");
for(j=1;j<=n;j++)
printf("%d %d %d\n",a[j].x,a[j].y,a[j].s);
printf("\n");*/
ax[n+1]=tt[k];
sort(a+1,a+1+n,cmp1);
int x1=0,x2=0,xt=n+1,xx1=0,xx2=0;
for(i=1;i<=n;i++)
{
if(a[i].x==10)
{
x1++;
b[x1]=a[i];
}
else if(a[i].s==10)
{
x2++;
c[x2]=a[i];
}
else
{
xt=i;
break;
}
}
int x3=0;
for(i=xt;i<=n;i++)
{
x3++;
d[x3]=a[i];
}
xx1=x1;
xx2=x2;
int ans=0;
int as=n+1;
if(x1>0)
{
as--;
ax[as]=b[x1];
x1--;
//ax[as]=a[xt-(xx2-x2)];
}
else
continue;
while(x2>0&&x1>0)
{
as--;
//ax[as]=a[xt-(xx2-x2)];
ax[as]=c[x2];
as--;
ax[as].x=10;
ax[as].y=0;
ax[as].s=10;
x1--;
x2--;
}
if(x2>0)
{
//----------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------
sort(d+1,d+1+x3,cmp2);
int d2=1,d2r=x2,d3=1,d3r=x3;
bool flag=true;
while(d2r-d2+1>0&&d3r-d3+1>0)
{
if(flag)
{
as--;
ax[as]=c[d2r];
d2r--;
flag=false;
}
else
{
/* //if(d[d3].x>ax[as].x)
if(d[d3].x*2+ax[as].x>=c[d2].x+ax[as].x*2||d2r-d2+1==1&&d[d3].x>ax[as].x)
{
as--;
ax[as]=d[d3];
d3++;
flag=true;
}
else
{
as--;
ax[as]=c[d2];
d2++;
}*/
if(d2r-d2+1==1)
{
if(d[d3].x>ax[as].x)
{
as--;
ax[as]=d[d3];
d3++;
flag=true;
}
else
{
as--;
ax[as]=c[d2];
d2++;
}
}
else
{
if(d[d3].x>ax[as].x)
{
as--;
ax[as]=d[d3];
d3++;
flag=true;
}
else
{
as--;
ax[as]=c[d2];
d2++;
}
}
}
}
if(d2r-d2+1>0)
{
while(d2r-d2+1>0)
{
as--;
ax[as]=c[d2];
d2++;
}
}
else if(d3r-d3+1>0)
{
while(d3r-d3+1>0)
{
as--;
ax[as]=d[d3];
d3++;
}
}
bool flag1=false,flag2=false;
ans=0;
for(j=1;j<=n+1;j++)
{
if(flag1)
ans+=(ax[j].s*2);
else if(flag2)
ans+=(ax[j].x*2+ax[j].y);
else
ans+=(ax[j].x+ax[j].y);
flag1=false;
flag2=false;
if(ax[j].x==10)
flag1=true;
else if(ax[j].s==10)
flag2=true;
}
ansx=max(ansx,ans);
int j;
for(i=1;i<=n-1;i++)
if(ax[i].s==10)
break;
//int tx=i;
for(int tx=1;tx<=n-1;tx++)
{
for(i=n-1;i>=1;i--)
{
// if(ax[i].x==10)
// {
score t=ax[i];
ax[i]=ax[tx];
ax[tx]=t;
ans=0;
bool flag1=false,flag2=false;
for(j=1;j<=n+1;j++)
{
if(flag1)
ans+=(ax[j].s*2);
else if(flag2)
ans+=(ax[j].x*2+ax[j].y);
else
ans+=(ax[j].x+ax[j].y);
flag1=false;
flag2=false;
if(ax[j].x==10)
flag1=true;
else if(ax[j].s==10)
flag2=true;
}
ansx=max(ansx,ans);
t=ax[i];
ax[i]=ax[tx];
ax[tx]=t;
// }
}
}
//----------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------
}
else if(x1>0)
{
while(x1>0)
{
as--;
ax[as].x=10;
ax[as].y=0;
ax[as].s=10;
x1--;
}
for(i=xt;i<=n;i++)
{
as--;
ax[as]=a[i];
}
bool flag1=false,flag2=false;
ans=0;
/* printf("\n");
for(j=1;j<=n+1;j++)
printf("%d %d %d\n",ax[j].x,ax[j].y,ax[j].s);
printf("\n");*/
for(j=1;j<=n+1;j++)
{
if(flag1)
ans+=(ax[j].s*2);
else if(flag2)
ans+=(ax[j].x*2+ax[j].y);
else
ans+=(ax[j].x+ax[j].y);
flag1=false;
flag2=false;
if(ax[j].x==10)
flag1=true;
else if(ax[j].s==10)
flag2=true;
}
ansx=max(ansx,ans);
}
}
printf("%d\n",ansx);
}
return 0;
}至此JSOI2014第二轮题目全部补全完毕
![bzoj 2208: [Jsoi2010]连通数](http://www.lydsy.com/JudgeOnline/images/2208.jpg)