[PA2014]Kuglarz
题目描述
魔术师的桌子上有 \(n\) 个杯子排成一行，编号为 \(1,2,…,n\)，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。
花费 \(c_{ij}\) 元，魔术师就会告诉你杯子 \(i,i+1,…,j\) 底下藏有球的总数的奇偶性。
采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？
输入格式
第一行一个整数 \(n\)。
第 \(i+1\) 行（\(1\le i\le n\)）有 \(n+1-i\) 个整数，表示每一种询问所需的花费。
其中 \(c_{ij}\)（对区间 \([i,j]\) 进行询问的费用，\(1\le i\le j\le n\)）为第 \(i+1\) 行第 \(j+1-i\) 个数。
输出格式
输出一个整数，表示最少花费。
样例 #1
样例输入 #1
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
样例输出 #1
7
提示
对于 \(100\%\) 的数据，\(1\le n\le 2\times 10^3\)，\(1\le c_{ij}\le 10^9\)。
思路
最开始想的区间dp 发现不是那么好能想出状态转移就放弃了 这个只能那部分分的解法
发现好像是选一些区间 将所有点填满即可 但是我们显然对于起始点的选定不是那么好确定
我们虚拟源点0
对于一个区间我们知道0，i-1 i，j 我们显然就知道了0，j 这就映射了我们前面的猜想
对于每一个i，j的边我们将i-1 j涂掉 那显然 我们可以抽象成最小生成树
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int p[N*N];
struct edge{
int a,b,w;
bool operator < (const edge &W)const{
return w<W.w;
}
}e[N*N];
int find(int x){
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
void solve() {
int n,m,cnt=0;cin>>n;m=0;
for(int i=n;i>=1;i--)m+=i;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++,cnt++){
e[cnt].a=i-1,e[cnt].b=j;
cin>>e[cnt].w;
}
}
sort(e,e+m);
for(int i=0;i<=n;i++)p[i]=i;
int res=0;cnt=0;
for(int i=0;i<m;i++){
int a=e[i].a,b=e[i].b,w=e[i].w;
if(find(a)==find(b))continue;
else p[find(a)]=find(b),res+=w,cnt++;
}
cout<<res<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}