题目描述
$n$ 个杯子，一些杯子里有小球。可以花费 $c_{i,j}$ 的代价询问从 $i$ 到 $j$ 号杯子中有球的杯子数量的奇偶性，求要知道每个杯子中是否有小球的最小代价。
思路
很有趣的一道题，一开始以为是区间 DP，但是原题 $2×10^9$ 的数据范围 $O(n^3)$ 复杂度直接去世。
要想知道 $pos$ 位置有没有小球，我们只需要知道任意的 $[a,pos]$ 和 $[a,pos+1]$ 的奇偶性就可以了（显然），进一步来说，我们只需要知道所有的 $[0,i]$ 的奇偶性就可以知道每个位置是否有小球了。
现在要求知道所有的 $[0,i]$ 的奇偶性的最小代价：假设我们现在知道了 $[0,i-1]$ 的奇偶性，那么我们只需要询问 $[i,j]$ 的奇偶性就可以知道 $[0,j]$ 的奇偶性了，反过来也是成立的 —— 那么对于 $[0,i]$ 和 $[0,j]$，我们只要知道一个，在花费 $c_{i,j}$ 的代价就可以知道另一个了。将每个 $[0,i]$ 看成点，每个这样的「知道」关系看作是点之间的无向边，具体来讲对于上面的例子就是点 $i$ 和 点 $j$ 之间有一条权值为 $c_{i,j}$ 的无向边。
于是我们就是要用最小的边权让所有点都联通，就是最小生成树啦。
Code
注意造出来的图比较稠密，请使用 Prim 算法（不过好像原题用 Kruskal 也能过）。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<queue>
#include<vector>
#include<utility>
#define int long long
#define fake false
using namespace std;
const int MaxN = 2003;
int n, ans, c[MaxN][MaxN], dis[MaxN];
bool visited[MaxN];
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline void Prim(){
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[0] = 0;
for(int i=0; i<n; i++){
int x = -1;
for(int j=0; j<=n; j++){
if(visited[j]) continue;
if(x == -1 || dis[j] < dis[x]) x = j;
}
visited[x] = !fake;
for(int j=0; j<=n; j++){
if(!visited[j]) dis[j] = min(dis[j], c[x][j]);
}
}
}
signed main(){
n = Read();
memset(c, 0x3f3f3f3f, sizeof(c));
for(int i=0; i<=n; i++)
c[i][i] = 0;
for(int i=0; i<n; i++){
for(int j=i+1; j<=n; j++){
c[i][j] = c[j][i] = Read();
}
}
Prim();
for(int i=1; i<=n; i++)
ans += dis[i];
printf("%lld", ans);
return 0;
}