标签：贪心，DP
题目
2.1 backgrounds 小O是一个很萌很萌的女孩子 2.2 content 有一段时间，小O对保龄球十分感兴趣，她特地去研究了一下保龄球的 规则。 一场比赛一共有n轮， 在每轮的一开始有10个瓶子，每一轮小O有两次扔球机会。一轮结束 后，瓶子会被重置。 如果小O某一轮中击倒了10个瓶子，称为“奥义”。 特别的，如果小O第一次扔球就击倒了10个瓶子，称为“全给”（不再 称为“奥义”）。 另外，如果小O在第n轮中打出了“全给”，那么她可以获得额外的一 轮。（只能获得一次） 最后的分数是这么计算的： 每次扔球的基础分是该次击倒的瓶子数目。 如果上一次是“全给”，则小O额外获得与这轮基础分相同的奖励分。 如果上一次是“奥义”，则小O额外获得与这轮的第一次扔球的基础分 相同的奖励分。 最后的总分是把所有分加起来。 现在给出小O的比赛情况，她现在想知道，通过重新排列每轮的顺序能 获得的最大得分是多少。 提醒：有奖励轮时第n轮必须是“全给”，重排后也是一样。 2.3 input format 第一行一个正整数n，表示预定的轮数。 接下来n行，每行两个正整数ai，bi，表示小O第i轮两次扔球分别击倒 的瓶子个数。 特别的，如果an = 10，则还有一行输入，表示奖励轮中小O两次扔球 分别击倒的瓶子个数。 2.4 output format 一行一个整数，表示最大可能得分。 2.5 sample input 2 3 7 10 0 5 2 2.6 sample output 44 2.7 sample explanation 将第一轮和第三轮互换一下，可以得到最大分数。 2.8 constraints 对于30%的数据，n ≤ 9 对于100%的数据，n ≤ 50，0 ≤ ai + bi ≤ 10
分析
直接粘题解了，贪心的思路不错，但是题目放在OI比赛里真的不好
好多人随机化然后AC了，逃）
我第一次听到出题人被骂sb的（删去）（不是我）
首先把所有 全给 接成一串,这样除了最后一个 全给 所有的 全给 都提供了10的收益 枚举一下最后一个 全给 后面接的是什么,可能有(1) 正常 (2) 奥义 (3) 奥义 + 正常 3种情况 把剩下的 正常 放在所有 全给 前面,再把 奥义 向序列中插入 因为不会改变 全给 获得的收益，只会得到一个第一投分数的收益,直接贪心就行 注意如果给了n+1行的话就必须保证序列倒数第二个是 全给 ,所以不存在(3)的情况
code
随机化
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=56;
int n;
bool flag=false;
pair<int,int>a[maxn];
int calc(){
if((flag)&&(a[n-1].first!=10))return -1;
int ans=0,p=1,q=1;
rep(i,1,n){
ans+=a[i].first*p+a[i].second*q;
if(a[i].first==10)p=q=2;
else if(a[i].first+a[i].second==10)p=2,q=1;
else p=q=1;
}
return ans;
}
int main()
{
srand(time(0));
n=read();
rep(i,1,n)a[i].first=read(),a[i].second=read();
if(a[n].first==10){
n++;flag=true;
a[n].first=read(),a[n].second=read();
}
int T=1000000,ans=calc();
while(T--){
int p=rand()%n+1,q=rand()%n+1;
swap(a[p],a[q]);
int ths=calc();
if(ths>=ans)ans=ths;else swap(a[p],a[q]);
}
cout<<ans<<endl;
return 0;
}
标程
#include <bits/stdc++.h>
using namespace std;
int N, n, a, b;
int strick;
vector<int>spare, normal;
int maxsum[20];
int base;
int ans, now;
int main() {
freopen("dierti10.in","r",stdin);
freopen("dierti10.out","w",stdout);
scanf("%d", &N);
while (scanf("%d%d", &a, &b) != EOF) {
n++;
base += a + b;
if (a + b != 10) {
normal.push_back(a);
maxsum[a] = max(maxsum[a], a + b);
} else if (a != 10) {
spare.push_back(a);
} else {
strick++;
}
}
if (strick) {
base += (strick - 1) * 10;
}
sort(spare.begin(), spare.end());
reverse(spare.begin(), spare.end());
for (int i = 0; i < int(normal.size()); i++) {
now = strick ? maxsum[normal[i]] : 0;
priority_queue<int>q;
for (int j = 1; j <= strick; j++) {
q.push(10);
}
for (int j = 0; j < int(normal.size()); j++) {
if (!strick || j != i) {
q.push(normal[j]);
}
}
for (int j = 0; j < int(spare.size()); j++) {
if (!q.empty()) {
now += q.top();
q.pop();
}
q.push(spare[j]);
}
ans = max(ans, now);
}
for (int i = 0; i < int(spare.size()); i++) {
now = strick ? 10 : 0;
priority_queue<int>q;
for (int j = 1; j <= strick; j++) {
q.push(10);
}
for (int j = 0; j < int(normal.size()); j++) {
q.push(normal[j]);
}
q.push(spare[i]);
for (int j = 0; j < int(spare.size()); j++) {
if (j != i) {
if (!q.empty()) {
now += q.top();
q.pop();
}
q.push(spare[j]);
}
}
ans = max(ans, now);
}
if (n == N) {
for (int i = 0; i < int(normal.size()); i++) {
for (int k = 0; k < int(spare.size()); k++) {
now = normal[i];
now += strick ? 10 : 0;
priority_queue<int>q;
for (int j = 1; j <= strick; j++) {
q.push(10);
}
for (int j = 0; j < int(normal.size()); j++) {
if (j != i) {
q.push(normal[j]);
}
}
q.push(spare[k]);
for (int j = 0; j < int(spare.size()); j++) {
if (j != k) {
if (!q.empty()) {
now += q.top();
q.pop();
}
q.push(spare[j]);
}
}
ans = max(ans, now);
if (now == 37) {
printf("%d %d\n", normal[i], spare[k]);
}
}
}
}
printf("%d\n", ans + base);
return 0;
}
