Luogu

LOJ

BZOJ

分析

太神了...看了好久才看懂...

先考虑一些性质:

  • 如果上一轮是全中,那么一定放第一轮最小的补中(可以让第一轮最大的补中放在其它补中后),或者总分最大的失误。
  • 如果上一轮是补中,那么一定放第一轮最大的。

可以发,我们要么取第一轮最小的补中,要么取第一轮最大的补中。

考虑最优解大概是什么样子,可以发现是全中补中交替放,最后再放失误,而第一个失误要么是第一轮最大的,要么是总分最大的。

但是由于有附加轮的存在,可能会有一个失误轮是特例。

于是得到这样一个做法:我们把补中按第一轮得分排序,枚举哪一轮是特例以及失误轮按第一轮排序还是按总分排序,然后 DP:设 $dp_{i,l,r,j,k,0/1/2}$ 表示放了前 $i$ 个全中,没放的补中在 $[l,r]$ 内,放了前 $k$ 个失误,放了 $k$ 个特例,放的最后一轮是失误/补中/全中的最大得分。转移比较多,详见代码。(然而 longge 说随便转移即可)

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50+1;

int n,s1=0,s2=0,s3=0,flag=0,ans=0;
struct Round { int x,y,s; } a[N],b[N],b_[N],sp;
inline int cmpx(Round x,Round y) { return x.x>y.x; }
inline int cmps(Round x,Round y) { return x.s>y.s; }

int dp[N][N][N][N][2][3];
inline int cw(int o,int x,int y) {
    if (o==0) return x+y;
    if (o==1) return (x<<1)+y;
    if (o==2) return (x+y)<<1;
}
inline void calc(int f) { int w;
    for (re int i=0;i<=s1;++i)
        for (re int l=0;l<=s2;++l)
            for (re int r=l;r<=s2;++r)
                for (re int j=0;j<=s3;++j)
                    for (re int k=0;k<=f;++k)
                        for (re int o=0;o<=2;++o)
                            dp[i][l][r][j][k][o]=-1;
    dp[0][0][s2][0][0][0]=0;
    for (re int i=0;i<=s1;++i)
        for (re int l=0;l<=s2;++l)
            for (re int r=s2;r>=l;--r)
                for (re int j=0;j<=s3;++j)
                    for (re int k=0;k<=f;++k)
                        for (re int o=0;o<=2;++o) {
                            if (dp[i][l][r][j][k][o]==-1) continue;
                            int useall=1,useother=1;
                            if (i+l+s2-r+j+k==n-2)
                                useall=flag,useother=flag^1;
                            if (useall&&i<s1) {
                                w=cw(o,10,0);
                                chkmax(dp[i+1][l][r][j][k][2],
                                       dp[i][l][r][j][k][o]+w);
                            }
                            if (!useother) continue;
                            if (l<r) {
                                w=cw(o,a[l+1].x,a[l+1].y);
                                chkmax(dp[i][l+1][r][j][k][1],
                                       dp[i][l][r][j][k][o]+w);
                                w=cw(o,a[r].x,a[r].y);
                                chkmax(dp[i][l][r-1][j][k][1],
                                       dp[i][l][r][j][k][o]+w);
                            }
                            if (j<s3) {
                                w=cw(o,b[j+1].x,b[j+1].y);
                                chkmax(dp[i][l][r][j+1][k][0],
                                       dp[i][l][r][j][k][o]+w);
                            }
                            if (k<f) {
                                w=cw(o,sp.x,sp.y);
                                chkmax(dp[i][l][r][j][1][0],
                                       dp[i][l][r][j][k][o]+w);
                            }
                        }
    for (re int i=0;i<=s2;++i)
        for (re int o=0;o<3;++o)
            chkmax(ans,dp[s1][i][i][s3][f][o]);
}

inline void solve(int f) {
    sort(b+1,b+s3+1,cmpx); calc(f);
    sort(b+1,b+s3+1,cmps); calc(f);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        int x=read(),y=read();
        if (x==10) { ++s1;
            if (i==n&&!flag) flag=1,++n;
        }
        else if (x+y==10) a[++s2]=(Round){x,y,x+y};
        else b[++s3]=(Round){x,y,x+y};
    }
    sort(a+1,a+s2+1,cmpx);
    solve(0);
    for (re int i=1;i<=s3;++i) {
        for (re int j=1;j<=s3;++j) b_[j]=b[j];
        sp=b[i]; int top=0;
        for (re int j=1;j<=s3;++j) if (j!=i) b[++top]=b_[j];
        --s3,solve(1),++s3;
        for (re int j=1;j<=s3;++j) b[j]=b_[j];
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 02 月 08 日 05 : 48 PM