Znzryb's Blog
0%

ABC-375-E-3 Team Division

Posted on Edited on

题目大意

给定 nn 个人，每个人有一个所属组别 teami∈{1,2,3}team_i \in \{1,2,3\} 和一个权重 sis_i。需要把所有人重新分到 3 组，使得每组权重和都等于总和的 1/31/3，并且最少改变人数（把一个人从原组分到别组算一次改变）。输出最少改变数；若无法平分则输出 −1-1。

AC代码

具体思路见此视频

【AtCoder 初学者竞赛 375比赛讲解】 【精准空降到 1:09:56】 https://www.bilibili.com/video/BV1UR26YnEpX/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=4196

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// E - 3 Team Division
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=110;
ll n,team[N],s[N],sum[4],S,object,dp[N][510][510],prefixSum[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>team[i]>>s[i];
        S+=s[i];
    }
    memset(dp,0x3f,sizeof(dp));
    register ll inf=dp[0][0][0];
    dp[0][0][0]=0;
    if(S%3!=0) {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++) {     // 就是算一个前缀和
        prefixSum[i]=prefixSum[i-1]+s[i];
    }
    object=S/3;
    for(int i=1;i<=n;++i) {
        for(int a=0;a<=object;++a) {
            for(int b=0;b<=object;++b) {
                register ll res=inf;
                if(s[i]<=a)
                    res=min(res,dp[i-1][a-s[i]][b]+(team[i] != 1));
                if(s[i]<=b)
                    res=min(res,dp[i-1][a][b-s[i]]+(team[i] != 2));
                if(s[i]<=prefixSum[i]-a-b)
                    res=min(res,dp[i-1][a][b]+(team[i] != 3));
                dp[i][a][b]=res;
            }
        }
    }
    ll ans= dp[n][object][object]==inf ? -1:dp[n][object][object];
    cout<<ans<<endl;
    return 0;
}
// AC https://atcoder.jp/contests/abc375/submissions/59007037

心路历程（WA，TLE，MLE……）