Gym102431G Game on the Tree

Link
结论\(1\)：只需要\(3\)个船夫，其中有\(2\)个船夫可能会在B,C岛停留。
结论\(2\)：将所有游客先按目的地分类，再按所需时间降序排序，那么在一条船上，前往同一个目的地的游客是目前所需时间最大的几个。
设\(f_{i,j,k,l}\)表示考虑前\(i\)个人已经，有\(j\)个去B岛的空位和\(k\)个去C岛的空位，同时外面还需要\(l\)个船夫的最小时间。其中\(i\in[1,n],j,k\in[0,2],l\in[-1,2]\)。
转移比较的多：
\(1.\)补两个需要的船夫。
\(2.\)补一个需要的船夫。
\(3.\)制造一个空位。
\(4.\)制造两个空位，需要一个船夫。
\(5.\)使用空位（去B可以蹭去C的空位）。
\(6.\)去B的空位升级为去C的空位。

#include<cstdio>
#include<cctype>
#include<utility>
#include<cstring>
#include<algorithm>
#define fi first
#define se second
using pi=std::pair<int,int>;
const int N=50007,inf=2e9;
int f[N][3][3][4];pi a[N];
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
void min(int&a,int b){a=a<b? a:b;}
int main()
{
    for(int Case=1,T=read();Case<=T;++Case)
    {
    int n=read(),ans=inf;
    for(int i=1;i<=n;++i) a[i]={read(),read()};
    std::sort(a+1,a+n+1,[](const pi&a,const pi&b){return a.se>b.se;}),memset(f,0x3f,sizeof f),f[0][0][0][1]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=2;~j;--j)
        for(int k=2;~k;--k)
            for(int l=3;~l;--l)
            if(a[i].fi==2)
            {
                if(j){min(f[i][j-1][k][l],f[i-1][j][k][l]);continue;}
                if(k) min(f[i][k-1][0][l],f[i-1][j][k][l]+a[i].se-1);
                if(l) min(f[i][0][k][l-1],f[i-1][j][k][l]+2*a[i].se+1);
                min(f[i][1][k][l],f[i-1][j][k][l]+2*a[i].se+1);
                if(l^3) min(f[i][2][k][l+1],f[i-1][j][k][l]+2*a[i].se+1);
            }
            else
            {
                if(k){min(f[i][j][k-1][l],f[i-1][j][k][l]);continue;}
                if(j) min(f[i][j-1][k][l],f[i-1][j][k][l]);
                if(l) min(f[i][j][0][l-1],f[i-1][j][k][l]+a[i].se+2);
                min(f[i][j][1][l],f[i-1][j][k][l]+a[i].se+2);
                if(l^3) min(f[i][j][2][l+1],f[i-1][j][k][l]+a[i].se+2);
            }
        for(int j=2;~j;--j) for(int k=2;~k;--k) for(int l=2;l<=3;++l) min(f[i][j][k][l-2],f[i][j][k][l]+3);
    }
    for(int j=0;j<=2;++j) for(int k=0;k<=2;++k) for(int l=0;l<=1;++l) min(ans,f[n][j][k][l]);
    printf("Case #%d: %d\n",Case,ans);
    }
}

Gym102431G Game on the Tree

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12499536.html