题目

点这里看题目。

题面太长，我懒得抄了。

分析

假设五种宝石最终需要的数量为 \(A,B,C,D,E\)，则取宝石需要的操作轮数为 \(\max\{A,B,C,D,E,\lceil\frac{A+B+C+D+E}{2}\rceil\}\)。

钦定 \(A,B,C,D,E\) 成为上式的最大值是容易的，但要控制 \(\lceil\frac{A+B+C+D+E}{2}\rceil\) 成为最大值却不容易。注意到，后一种情况计算时只需要知道 \(A+B+C+D+E\)，而这个值小到可以直接枚举（或者说塞进状态里），所以考虑求出 \(A,B,C,D,E\) 分别为上式最大值时的操作方案数量，一减就可以得到后一种情况的数量了。复杂度为 \(O(n^2M^2)\)。

虽然复杂度不是很好，但是确实很有意思。

另一种想法就是在 DP 过程中算出来最小的取宝石次数。

很简单的错误的思路：每次任意地取出来两个不同的宝石，最后可能剩下一种宝石，那就单独取它。之所以它是错的，是因为这个取法就等价于每次任意取......

但是这个操作起来真的很简单啊！怎么修一下这个做法呢？

如果任意取的过程可以时刻保证 \(2\max<\sigma\)，那么这个任意取的次数就是最小次数。反过来，如果任意取的过程中的某一时刻 \(2\max\ge \sigma\)，那么我们就应该开始将最多的一种和别的宝石一起取了。可操作的地方就来了：我们可以任意地钦定什么时候开始做 \(2\max\ge \sigma\) 的操作，显然在不合适的时候进行操作方式的切换的话操作数量不会变小。更进一步地，我们也可以必要的时候，选择从 \(2\max\ge \sigma\) 的操作切换回任意选的操作。当然，为了保证取得到最小值，我们需要包含每一种必要的切换策略。

那么，考虑 \(f_{i,j,t,k}\) 表示任意选过程中，当前桌子上的两张牌为 \(i,j\)，且目前剩下了 \(k\) 个第 \(t\) 种宝石没有取得时最小取宝石轮数；\(g_{i,j,t,k}\) 表示认为第 \(t\) 种宝石数量会不少于一半时，当前桌子上两张牌为 \(i,j\)，且其它类型的宝石总共剩 \(k\) 个没有取得时的最小取宝石轮数。

我们的策略同加入宝石的顺序无关，因此我们只需要考虑一次性加入多个同种宝石的转移。也就是：

• 考虑在 \(f\) 的 \((t,k)\) 状态时，加入 \(b\) 个 \(a\) 种宝石。

  • 如果 \(t=b\)，那么宝石数量加起来，转移到 \(f\) 的 \((t,k+b)\) 状态。

  • 如果 \(t\neq b\)，还有选择：

    • 一种选择是任意取。那么当 \(k\le b\) 的时候，可以转移到 \(f\) 的 \((a,b-k)\) 状态；当 \(k>b\) 的时候，则可以转移到 \(f\) 的 \((t,k-b)\) 状态。

    • 另一种选择则是，先任意取一些宝石，然后切换到 \(2\max\ge\sigma\) 的操作。也即，先取 \(x\) 对宝石（应有 \(0\le x\le \min\{k,b\}\)），然后钦定 \(t'\)（应有 \(t'\neq t,t'\neq a\)）为最多的宝石，最终转移到 \(g\) 的 \((t',b+k-2x)\)。

• 考虑在 \(g\) 的 \((t,k)\) 状态时，加入 \(b\) 个 \(a\) 种宝石。

  • 如果 \(a\neq t\)，那么宝石数量加起来，转移到 \(g\) 的 \((t,k+b)\) 状态。

  • 如果 \(a=t\)，那么当 \(b\le k\) 的时候，可以转移到 \(g\) 的 \((t,k-b)\) 状态；当 \(b>k\) 的时候，会剩下一些 \(t\) 种宝石，此时可以切换回“任意选”的操作（因为这也不会出现 \(t\) 以外的宝石内部匹配的情况），于是转移到 \(f\) 的 \((t,b-k)\) 状态。

直接转移的复杂度为 \(O(n^2M^2)\)，主要矛盾在 \(f\) 的 \(t\neq b\) 部分。

分类讨论，如果 \(k\le b\)，那么会对 \([b-k,b+k]\) 中下标为某一奇偶性的位置和一个等差数列取较小值，因为这样的区间一定跨过 \(b\) 这个点，所以直接从这里断开并打标记。如果 \(k<b\)，则会对 \([k-b,k+b]\) 中的下标做同样的操作，因为这样的区间长度固定，所以可以用单调队列维护。复杂度因而被优化为了 \(O(n^2M)\)。

代码

但是我代码常数好大啊！！！

#include <bits/stdc++.h>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int INF = 0x3f3f3f3f;
const int MAXN = 55, MAXM = 2005;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

struct DPBase {
    int f[5][MAXM], g[5][MAXM];

    DPBase() {
        memset( f, 0x3f, sizeof f );
        memset( g, 0x3f, sizeof g );
    }

    inline void Clear( const int &m ) {
        rep( j, 0, 4 )
            memset( f[j], 0x3f, ( m + 1 ) << 2 ),
            memset( g[j], 0x3f, ( m + 1 ) << 2 );
    }
};

struct Queue {
    int q[MAXM], h, t;

    Queue(): q{}, h( 1 ), t( 0 ) {}

    inline bool Empty() const { return h > t; }
    inline void Clear() { h = 1, t = 0; }
    inline void Push( const int &x ) { q[++ t] = x; }
    inline  int Front() const { return q[h]; }
    inline  int Back() const { return q[t]; }
    inline void PopFront() { h ++; }
    inline void PopBack() { t --; }
};

DPBase dp[2][MAXN], tmp[2];

int cost[MAXN][5], disc[MAXN][5], pref[MAXN][5];
int suCost[5];

int N, M;

inline void ChkMin( int &x, const int &v ) {
    x = x < v ? x : v;
}

inline void operator += ( DPBase &a, const DPBase &b ) {
    rep( i, 0, 4 ) rep( j, 0, M ) ChkMin( a.f[i][j], b.f[i][j] );
    rep( i, 0, 4 ) rep( j, 0, M ) ChkMin( a.g[i][j], b.g[i][j] );
}

inline void Transfer( DPBase &tar, const DPBase &src, const int &a, const int &b ) {
    static Queue q[2];
    static int tag[MAXM] = {};
    
    // 转移 f
    rep( j, 0, M - b )
        ChkMin( tar.f[a][j + b], src.f[a][j] );
    rep( i, 0, 4 ) if( i ^ a ) {
        memset( tag, 0x3f, ( M + 1 ) << 2 );

        rep( j, 0, b ) ChkMin( tar.f[a][b - j], src.f[i][j] + j );
        rep( j, b + 1, M ) ChkMin( tar.f[i][j - b], src.f[i][j] + b );
        for( int j = 0 ; j <= b && j <= M - b ; j ++ ) {
            ChkMin( tag[b + j], src.f[i][j] );
            ChkMin( tag[b - j], src.f[i][j] + j );
        }
        per( j, M - 2, b ) ChkMin( tag[j], tag[j + 2] + 1 );
        rep( j, 2, b ) ChkMin( tag[j], tag[j - 2] - 1 );
        q[0].Clear(), q[1].Clear();
        for( int j = b + 1, o ; j <= M ; j ++ ) {
            o = ( j ^ b ) & 1;
            while( ! q[o].Empty() && q[o].Front() < j - b ) q[o].PopFront();
            while( ! q[o].Empty() && src.f[i][j] + ( ( j + b ) >> 1 ) <= src.f[i][q[o].Back()] + ( ( q[o].Back() + b ) >> 1 ) ) q[o].PopBack();
            q[o].Push( j );
            o = j & 1;
            if( ! q[o].Empty() )
                ChkMin( tag[j], src.f[i][q[o].Front()] + ( ( q[o].Front() + b - j ) >> 1 ) );
        }
        q[0].Clear(), q[1].Clear();
        for( int j = M - b, o ; j >= 0 ; j -- ) {
            o = ( j ^ b ) & 1;
            while( ! q[o].Empty() && q[o].Front() > j + b ) q[o].PopFront();
            if( j > b ) {
                while( ! q[o].Empty() && src.f[i][j] + ( ( j + b ) >> 1 ) <= src.f[i][q[o].Back()] + ( ( q[o].Back() + b ) >> 1 ) ) q[o].PopBack();
                q[o].Push( j );
            }
            o = j & 1;
            if( ! q[o].Empty() )
                ChkMin( tag[j], src.f[i][q[o].Front()] + ( ( q[o].Front() + b - j ) >> 1 ) );
        }
        rep( j, 0, 4 ) if( j ^ i && j ^ a )
            rep( k, 0, M ) ChkMin( tar.g[j][k], tag[k] );
    }
    // 转移 g
    rep( i, 0, 4 ) if( i ^ a ) rep( j, 0, M - b ) 
        ChkMin( tar.g[i][j + b], src.g[i][j] );
    rep( j, 0, b - 1 ) ChkMin( tar.f[a][b - j], src.g[a][j] + j );
    rep( j, b, M ) ChkMin( tar.g[a][j - b], src.g[a][j] + b );
}

int main() {
    Read( N );
    rep( i, 1, N ) {
        rep( j, 0, 4 ) Read( cost[i][j] ), suCost[j] += cost[i][j];
        rep( j, 0, 4 ) Read( disc[i][j] ), pref[i][j] = pref[i - 1][j] + disc[i][j];
    }
    rep( j, 0, 4 ) M = std :: max( M, suCost[j] );
    int pre = 1, nxt = 0;
    rep( j, 0, 4 ) dp[nxt][1].f[j][0] = 0;
    rep( i, 2, N + 1 ) {
        pre ^= 1, nxt ^= 1;
        rep( j, 1, i ) dp[nxt][j].Clear( M );
        rep( j, 1, i - 1 ) {
            // 转移 j
            tmp[0] = dp[pre][j];
            rep( k, 0, 4 )
                tmp[~ k & 1].Clear( M ), Transfer( tmp[~ k & 1], tmp[k & 1], k, std :: max( 0, cost[j][k] - ( pref[i - 1][k] - disc[j][k] ) ) );
            dp[nxt][i] += tmp[1];
            // 转移 i
            if( i > N ) continue;
            tmp[0] = dp[pre][j];
            rep( k, 0, 4 )
                tmp[~ k & 1].Clear( M ), Transfer( tmp[~ k & 1], tmp[k & 1], k, std :: max( 0, cost[i][k] - ( pref[i - 1][k] - disc[j][k] ) ) );
            dp[nxt][j] += tmp[1];
        }
    }
    int ans = INF;
    rep( i, 0, 4 ) {
        ChkMin( ans, dp[nxt][N + 1].f[i][0] );
        ChkMin( ans, dp[nxt][N + 1].g[i][0] );
        rep( j, 1, M )
            ChkMin( ans, dp[nxt][N + 1].f[i][j] + j );
    }
    Write( ans + N ), putchar( '\n' );
    return 0;
}