【AT_abc375_e】E - 3 Team Division 题解

· · 题解

一个 DP 问题，赛时错了一点点无缘 AC。

题目传送门

Translation

有 N 人分成三个小组。

第 i 个人有两个属性：初始分组 A_i，魔怔值 B_i。

其中 A_i\in \{1,2,3\},\sum B\leq 1500。

现在要求您为这些人重新分组：对于第 i 个人，可以保持分组不变，也可以为他切换组别。要求分组后每个组别的魔怔值总和相等。

求最少的切换组别的次数。

Solution

Part 1

大水题一个，如果你知道记忆化搜索。

容易设计出一个非常暴力的 DP：

转移时不妨假设第 i 个人初始在 1 组。

如果这样设计状态发现时间空间复杂度都是 O(N(\sum B)^3)。但发现 \sum B 不必开满，每个状态只需到 \dfrac{1}{3}\sum B，这是因为平均数原理。

但这样在渐进意义下仍然不对，只能减小常数。

实际上 c=\sum B-a-b，所以 c 不必计入状态，所以时空复杂度被优化到 O(N(\sum B)^2)，它可以通过本道题。

#include <bits/stdc++.h>

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937_64 rnd64(std::chrono::steady_clock::now().time_since_epoch().count());

const int N=102;
const int M=1501;

int n;
int mem[N][M][M];
vector<int> A,B;

int dp(int i,int a,int b,int c)
{
    if(a<0||b<0||c<0) return N;
    int& ans=mem[i][a][b];
    if(i==n+1)
    {
        if(a==0&&b==0&&c==0) return 0;
        else return N;
    }
    if(ans!=-1) return ans;
    ans=N;
    // 决策1：不换。
    if(A[i]==1) ans=min(ans,dp(i+1,a-B[i],b,c));
    else if(A[i]==2) ans=min(ans,dp(i+1,a,b-B[i],c));
    else if(A[i]==3) ans=min(ans,dp(i+1,a,b,c-B[i]));
    // 决策2：换。
    if(A[i]==1) ans=min(ans,1+min(dp(i+1,a,b-B[i],c),dp(i+1,a,b,c-B[i])));
    else if(A[i]==2) ans=min(ans,1+min(dp(i+1,a-B[i],b,c),dp(i+1,a,b,c-B[i])));
    else if(A[i]==3) ans=min(ans,1+min(dp(i+1,a-B[i],b,c),dp(i+1,a,b-B[i],c)));
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    A.resize(n+1),B.resize(n+1);
    int sum=0;
    rep(i,1,n) cin>>A[i]>>B[i],sum+=B[i];
    int u=sum/3,ans=M;
    memset(mem,-1,sizeof(mem));
    if(sum%3!=0){cout<<-1<<endl;return 0;}
    ans=dp(1,u,u,u);
    cout<<(ans>=N?-1:ans);
}

一个技巧是，只有 (\sum B) \equiv 0\pmod N 时才有可能有解。

Part 2

本解法属于恶搞做法。

最近在做分层图，我的魔怔值增高，故意将此题抽象成分层图问题。

对于每层图，是一个连接 1,2,\cdots,N 的链，每个边权为 0。

对于每个点 u，考虑到转移方式和 DP 的解法类似，于是记 dis(i,a,b) 表示从 (1,0,0) 这个点到 (i,a,b) 这个点的最短路。a 表示分组 1 的魔怔值和，b 表示分组 2 的魔怔值和。

上面已经介绍了同层图的建图方式，然后考虑一下建跨层边的方法，其实也和 DP 很类似，仿照 DP 的转移方式，不妨设第 i 个人的初始分组为 1：

最后求 (1,0,0) 到 (N+1,\frac{1}{3}\sum B,\frac{1}{3}\sum B) 的最短路。

Conclusion

这种题数据范围小，是一个很一眼的 DP 题。一般的最小值对应最短路，可以使用图论最短路解决；一般的最大值对应最长路，通常用 DP 解决。

关于 SPFA，她死了。