AtCoder Beginner Contest 375 E - 3 Team Division
题目大意
有
n
n
n个数字，初始时将它们分成了3组
现在可以进行一个操作：将一个数从某一组换到另外一组
问最后能否使三组数组内数字之和相等，若不能则输出
−
1
-1
−1，反之则输出最少操作次数
思路
真是一道阳间的DP啊啊啊啊
首先若是
∑
i
=
1
n
a
i
\sum_{i=1}^{n}a_i
∑i=1nai 不是n的倍数，显然无法操作成功然后…我卡了半天没有想法赛时直接没交
于是我们不妨从数据范围入手，注意到
n < = 100 ， ∑ b i < = 1500 n<=100，\sum b_i<=1500 n<=100，∑bi<=1500
属于那种搜索一定会T，正解是奇形怪状的DP的抽象题
我们不妨设
f
[
i
]
[
j
]
[
k
]
[
x
]
f[i][j][k][x]
f[i][j][k][x] 表示处理了前
i
i
i个数，第1组总和是
j
j
j，第2组总和是
k
k
k，第3组总和是
x
x
x 所需要操作的最小次数，然后必然是MLE了
注意到前两组数的总和一旦确定，第三组数的总和必然是一定的，因此最后一维可以直接扔掉，类比背包计数问题，我们可以得出这样一个状态转移方程
假设当前处理的第
i
i
i 个数属于第一组，我们有
f
[
i
]
[
j
]
[
k
]
=
m
i
n
(
f
[
i
]
[
[
j
]
[
k
]
[
,
f
[
i
−
1
]
[
j
−
b
[
i
]
]
[
k
]
)
f[i][j][k]=min(f[i][[j][k][,f[i-1][j-b[i]][k])
f[i][j][k]=min(f[i][[j][k][,f[i−1][j−b[i]][k])
直接填入第一组，不消耗操作次数
f
[
i
]
[
j
]
[
k
]
=
m
i
n
(
f
[
i
]
[
[
j
]
[
k
]
[
,
f
[
i
−
1
]
[
j
]
[
k
−
b
[
i
]
]
+
1
)
f[i][j][k]=min(f[i][[j][k][,f[i-1][j][k-b[i]]+1)
f[i][j][k]=min(f[i][[j][k][,f[i−1][j][k−b[i]]+1)
从第一组切换到第二组
f
[
i
]
[
j
]
[
k
]
=
m
i
n
(
f
[
i
]
[
[
j
]
[
k
]
[
,
f
[
i
−
1
]
[
j
]
[
k
]
+
1
)
f[i][j][k]=min(f[i][[j][k][,f[i-1][j][k]+1)
f[i][j][k]=min(f[i][[j][k][,f[i−1][j][k]+1)
从第一组切换到第三组
后续
a
[
i
]
=
2
,
3
a[i]=2,3
a[i]=2,3 同理可得
最后答案是
f
[
n
]
[
s
u
m
/
3
]
[
s
u
m
/
3
]
f[n][sum/3][sum/3]
f[n][sum/3][sum/3]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define rep(i,x,y) for(ll i=x;i<=y;++i)
#define per(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=520,inf=1e18;
ll n,a[V],c[V];
ll sum,f[V][V][V];//f[i][j][k] 前i个人 1 j 2 k 3 sum-j -k 的最少次数（压去一维）
inline ll in()
{
ll res=0,f=1;
char ch;
while((ch=getchar())<'0'||ch>'9')
if(ch=='-') f=-1;
res=res*10+ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return res*f;
}
inline void put(ll x)
{
if(x<0) putchar('-'),x*=-1;
if(x>9) put(x/10);
putchar(x%10+48);
}
int main()
{
n=in();
rep(i,1,n)
{
c[i]=in(),a[i]=in();
sum+=a[i];
}
if(sum%3)
{
printf("-1");
return 0;
}
rep(i,0,n)
rep(j,0,500)
rep(k,0,500)
f[i][j][k]=inf;
f[0][0][0]=0;
rep(i,1,n)
{
switch(c[i])
{
case(1) :
{
per(j,500,a[i])
per(k,500,0)
f[i][j][k]=min(f[i][j][k],f[i-1][j-a[i]][k]);//直接把b[i]填进来
per(j,500,0)
per(k,500,a[i])
f[i][j][k]=min(f[i][j][k],f[i-1][j][k-a[i]]+1);//b[i]切换到2
per(j,500,0)
per(k,500,0)
f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+1);//b[i]切换到3
break ;
}//后续同理
case(2) :
{
per(j,500,0)
per(k,500,a[i])
f[i][j][k]=min(f[i][j][k],f[i-1][j][k-a[i]]);//直接把b[i]填进来
per(j,500,a[i])
per(k,500,0)
f[i][j][k]=min(f[i][j][k],f[i-1][j-a[i]][k]+1);//b[i]切换到1
per(j,500,0)
per(k,500,0)
f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+1);//b[i]切换到3
break ;
}
default :
{
per(j,500,0)
per(k,500,0)
f[i][j][k]=min(f[i][j][k],f[i-1][j][k]);//直接把b[i]填进来
per(j,500,a[i])
per(k,500,0)
f[i][j][k]=min(f[i][j][k],f[i-1][j-a[i]][k]+1); //b[i]切换到1
per(j,500,0)
per(k,500,a[i])
f[i][j][k]=min(f[i][j][k],f[i-1][j][k-a[i]]+1);//b[i]切换到1
break ;
}
}
}
if(f[n][sum/3][sum/3]==inf) printf("-1");
else printf("%lld",f[n][sum/3][sum/3]);
return 0;
}