暗藏玄机的小题 2023-01-01 00:00 folder 题解Solution label 中文Chinese, 归档Archived

题目难度: NOIP / USACO Gold

题目分类: 图论

题目大意: [PA2014]Kuglarz

魔术师的桌子上有 \(n\) 个杯子排成一行, 有些杯子地下有小球

花费 \(c(i,j)\) 的价格, 魔术师就会告诉你杯子 \(i\) 到杯子 \(j\) 内藏有小球的个数的奇偶性

采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

\(n≤2\times 10^3\)

题目答案:

1. 可以发现 \(c(i,i)\) 可以得到一个 \(i\) 杯子的信息

2. 可以发现已知 \(c(i,j)\) 和 \(c(i,j-1)\) 可以得到杯子 \(j\) 的信息

区间DP? 陷阱!

区间DP是 \(O(n^3)\) 的, 同时, 需要枚举的断点 \(k\) 是可以在 \([i.j]\) 外面的范围内的

第一次尝试的代码

#include"bits/stdc++.h"
using namespace std;

const int maxn = 2e3+5;
int dp[maxn][maxn];
int c[maxn][maxn];
int main () {
    int n;cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for (int i=1;i<=n;i++) {
        for (int j=i;j<=n;j++) cin>>c[i][j];
        dp[i][i] = c[i][i];
    }
    for (int len=2;len<=n;len++) {
        for (int i=1;i+len-1<=n;i++) {
            int j = i+len-1;
            for (int k=i;k<=j;k++) {
                int cost = 0;
                if (k!=i) cost += dp[i][k-1];
                if (k!=j) cost += dp[k+1][j];
                dp[i][j] = min(dp[i][j],cost+c[i][j]);
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
}

继续推导, 不妨把每条信息当作一个线段

将 \(c(i,j)\) 替换成 \([i,j+1]\) 的区间

|--1--|--2--|--3--|--4--|--5--|--6--|--7--|
<----->                                       c(1,1) = [1,2]
<----------------->                           c(1,3) = [1,4]

已知 \([1,2]\), \([1,4]\), 显然可以得知 \([2,4]\), 即 \(c(2,3)\)

总结规律

1. \([x,x+1]\) 代表一个杯子的信息

2. 若 \([a,b]\) \([b,c]\), 则 \([b,c]\)

3. 若 \([a,b]\) \([a,c]\), 则 \([b,c]\)

这是一个图上信息的传递, 可以转化为图论问题

则此问题等价于花费多少的价钱可以使得图联通, 即把上图中的 | 当作一个个节点, 每条边链接两个 |

我们需要使得所有的 | 联通, 最小生成树即可, \(O(n^2\log n)\)

优雅

#include"bits/stdc++.h"
typedef long long ll;
using namespace std;

const int maxn = 2e3+5;
int f[maxn];
int cost[maxn][maxn];
int _find (int x) {
    if (f[x]==x) return x;
    f[x] = _find(f[x]);
    return f[x];
}
struct Edge {
    int u,v,w;
};
vector<Edge> v;
bool cmp (Edge a, Edge b) {
    return a.w<b.w;
}
ll Kruskal (int n) {
    sort(v.begin(),v.end(),cmp);
    int cnt = 0;
    ll ans = 0;
    for (int i=0;i<v.size();i++) {
        int U = v[i].u;
        int V = v[i].v;
        int W = v[i].w;
        int fu = _find(U);
        int fv = _find(V);
        if (fu==fv) continue;
        f[fu] = fv;
        ans += W;
        cnt++;
        if (cnt==n) return ans;
    }
}

int main () {
    int n;cin>>n;
    for (int i=1;i<=n+1;i++) f[i] = i;
    for (int i=1;i<=n;i++) {
        for (int j=i;j<=n;j++) {
            cin>>cost[i][j+1];
            v.push_back({i,j+1,cost[i][j+1]});
        }
    }
    cout<<Kruskal(n)<<endl;
}