UOJ #811 - 【UNR #7】璀璨宝石 80分补题
等价于我钦定一个激活顺序，然后计算每张卡牌需要 5 种颜色数量，求个和。记第 \(i\) 种颜色的总数量为 \(c_i\)，那么如果 \(c_i\) 中存在绝对众数那么答案就是 \(\max c_i\)，否则答案是 \(\lceil\dfrac{\sum c_i}{2}\rceil\)。
subtask 1：暴力枚举每次选两者中的哪一者。
subtask 2~4：由于只有两种有用的颜色，直接设 \(dp_{i,j,k}\) 表示目前有 \(i,j\) 两个可选卡牌，\(c_0=k\) 的情况下 \(c_1\) 的最小值。最后求解答案是容易的。
subtask 5~6：一种很直观的思路将所有情况分为存在绝对众数和不存在绝对众数两种情况，有绝对众数的情况是容易的，直接枚举绝对众数，然后状态里记录一维表示目前绝对众数的 \(c_i\) 与非绝对众数的 \(c_i\) 之和的差值是多少，DP 值表示此种情况下绝对众数的 \(c_i\) 的最小值。但是你会发现这样没法处理不存在绝对众数的情况。因此考虑换个思路，我们发现，对于任意长度为 \(5\) 的序列 \(c\)，都会存在一个位置 \(p\) 满足 \(\sum\limits_{i=0}^{p-1}c_i\) 和 \(\sum\limits_{i=p+1}^4c_i\) 都不超过总和的一半，暴力枚举这个位置 \(p\)，然后 \(dp_{i,j,sl,sm}\) 表示目前有 \(i,j\) 两张可选卡牌，\(\sum\limits_{i=0}^{p-1}c_i=sl,c_p=sm\) 的情况下 \(\sum\limits_{i=p+1}^4c_i\) 的最小值，然后最终状态就考虑如果 \(\sum\limits_{i=0}^{p-1}c_i,\sum\limits_{i=p+1}^4c_i\) 都不超过一半，那么对 \(c_i\) 是否过半分情况讨论，如果过半说明其是绝对众数，用 \(sm\) 更新答案，否则用总和一半上取整更新答案。时间复杂度 \(n^2m^2\)。
const int MAXN=50;
const int MAXS=300;
const int INF=0x3f3f3f3f;
int n,a[MAXN+5][5],b[MAXN+5][5],suma[MAXN+5][5],sumb[MAXN+5][5],res=INF;
namespace sub1{
int sum[5],cur[5],mn=1e9;
int calc(vector<int>v){
memset(sum,0,sizeof(sum));memset(cur,0,sizeof(cur));
for(int x:v){
for(int i=0;i<5;i++)sum[i]+=max(a[x][i]-cur[i],0);
for(int i=0;i<5;i++)cur[i]+=b[x][i];
}pii mx=mp(-1,0);
for(int i=0;i<5;i++)chkmax(mx,mp(sum[i],i));
int ss=0;
for(int i=0;i<5;i++)if(i!=mx.se)ss+=sum[i];
if(mx.fi>ss)return mx.fi;
else return (mx.fi+ss+1)>>1;
}
void dfs(int x,int y,vector<int>vec){
if(x==n+1){
vec.pb(y);chkmin(mn,calc(vec));
return;
}vec.pb(x);dfs(x+1,y,vec);vec.ppb();
vec.pb(y);dfs(x+1,x,vec);vec.ppb();
}
void solve(){dfs(2,1,vector<int>{});printf("%d\n",mn+n);}
}
namespace sub2{
const int MAXS=2000;
const int INF=0x3f3f3f3f;
int dp[MAXN+5][MAXN+5][MAXS+5];
bool check(){
for(int i=1;i<=n;i++){
bool flg=0;
if(!a[i][2]&&!a[i][3]&&!a[i][4])flg=1;
if(!b[i][2]&&!b[i][3]&&!b[i][4])flg=1;
if(!flg)return 0;
}return 1;
}
int calc(int A,int B,int C,int D,int E){
int mx=max(max(max(A,B),max(C,D)),E);
if(mx*2>A+B+C+D+E)return mx;
else return (A+B+C+D+E+1)>>1;
}
void solve(){
memset(dp,63,sizeof(dp));dp[2][1][0]=0;
for(int i=2;i<=n+1;i++)for(int j=1;j<i;j++)for(int k=0;k<=MAXS;k++)if(dp[i][j][k]<INF){
vector<int>nd(5),hav(5);
for(int t=0;t<5;t++)hav[t]=sumb[i-1][t]-b[j][t];
for(int t=0;t<5;t++)nd[t]=max(a[j][t]-hav[t],0);
chkmin(dp[i+1][i][k+nd[0]],dp[i][j][k]+nd[1]);
if(i!=n+1){
for(int t=0;t<5;t++)nd[t]=max(a[i][t]-hav[t],0);
chkmin(dp[i+1][j][k+nd[0]],dp[i][j][k]+nd[1]);
}
}
for(int k=0;k<=MAXS;k++)if(dp[n+2][n+1][k]<INF){
chkmin(res,calc(k,dp[n+2][n+1][k],suma[n][2],suma[n][3],suma[n][4]));
}
printf("%d\n",res+n);
}
}
namespace sub3{
int dp[2][MAXN+5][MAXS*5+5][MAXS+5],sum_lft[MAXN+5];
void work(int p){
memset(dp,63,sizeof(dp));memset(sum_lft,0,sizeof(sum_lft));
int pre=1,cur=0;dp[pre][1][0][0]=0;
for(int i=1;i<=n+1;i++)for(int j=0;j<p;j++)sum_lft[i]+=suma[i][j];
for(int i=2;i<=n+1;i++){
for(int j=1;j<=i;j++)for(int sl=0;sl<=sum_lft[i];sl++)for(int sm=0;sm<=suma[i][p];sm++)
dp[cur][j][sl][sm]=INF;
for(int j=1;j<i;j++)for(int sl=0;sl<=sum_lft[i-1];sl++)for(int sm=0;sm<=suma[i-1][p];sm++){
if(dp[pre][j][sl][sm]<INF){
vector<int>nd(5),hav(5);
for(int t=0;t<5;t++)hav[t]=sumb[i-1][t]-b[j][t];
for(int t=0;t<5;t++)nd[t]=max(a[j][t]-hav[t],0);
int nsl=sl,nsm=sm,nv=dp[pre][j][sl][sm];
for(int t=0;t<p;t++)nsl+=nd[t];nsm+=nd[p];
for(int t=0;t<5;t++)nv+=nd[t];
chkmin(dp[cur][i][nsl][nsm],nv);
if(i!=n+1){
for(int t=0;t<5;t++)nd[t]=max(a[i][t]-hav[t],0);
nsl=sl,nsm=sm,nv=dp[pre][j][sl][sm];
for(int t=0;t<p;t++)nsl+=nd[t];nsm+=nd[p];
for(int t=0;t<5;t++)nv+=nd[t];
chkmin(dp[cur][j][nsl][nsm],nv);
}
}
}swap(pre,cur);
}
for(int sl=0;sl<=sum_lft[n];sl++)for(int sm=0;sm<=suma[n][p];sm++){
if(dp[pre][n+1][sl][sm]<INF){
int sr=dp[pre][n+1][sl][sm]-sl-sm,sum=dp[pre][n+1][sl][sm];
if(sr*2<=sum&&sl*2<=sum){
if(sm*2>sum)chkmin(res,sm);
else chkmin(res,sum+1>>1);
}
}
}
}
void solve(){
for(int i=0;i<5;i++)work(i);
printf("%d\n",res+n);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=0;j<5;j++)scanf("%d",&a[i][j]);
for(int j=0;j<5;j++)scanf("%d",&b[i][j]);
}
for(int i=1;i<=n+1;i++)for(int j=0;j<5;j++)suma[i][j]=suma[i-1][j]+a[i][j];
for(int i=1;i<=n+1;i++)for(int j=0;j<5;j++)sumb[i][j]=sumb[i-1][j]+b[i][j];
if(n<=20)sub1::solve();
else if(sub2::check())sub2::solve();
else sub3::solve();
return 0;
}