### naive 的瓶子

#### 代码

#include <bits/stdc++.h>
#define ll long long
#define inf 1ll<<60
#define maxn 301
using namespace std;
ll f[maxn][maxn][maxn];
int n,T,a[maxn];
void chkmin(ll &x,ll y){x=x<y?x:y;}
void Solve(){
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",a+i),f[i][i][i]=0;
for (int len=1;len<n;len++){
for (int i=1,j=len;j<=n;i++,j++){
for (int k=i;k<=j;k++){
int bx=(a[i-1]!=a[k]),by=(a[j+1]!=a[k]);
if (i>1){
chkmin(f[k][i-1][j],f[k][i][j]+1ll*a[i-1]*a[k]*bx);
chkmin(f[i-1][i-1][j],f[k][i][j]+1ll*a[i-1]*a[k]*(j-i+1)*bx);
}
if (j<n){
chkmin(f[k][i][j+1],f[k][i][j]+1ll*a[j+1]*a[k]*by);
chkmin(f[j+1][i][j+1],f[k][i][j]+1ll*a[j+1]*a[k]*(j-i+1)*by);
}
}
}
}
ll ans=inf;
for (int i=1;i<=n;i++) chkmin(ans,f[i][1][n]);
printf("%lld\n",ans);
}
int main(){
freopen("colour.in","r",stdin);
freopen("colour.out","w",stdout);
scanf("%d",&T);
while(T--) Solve();
}


#### 代码

#include <bits/stdc++.h>
#define ll long long
#define maxn 500100
#define mid ((l+r)>>1)
using namespace std;
struct Edge{
int from,to,val;
Edge(int a=0,int b=0,int c=0){
from=a,to=b,val=c;
}
bool operator < (const Edge &x) const{
return val<x.val;
}
}e[maxn],a[maxn];
int n,m,L,fa[maxn],size[maxn],c[maxn];
int root[maxn],ls[maxn<<6],rs[maxn<<6],tree[maxn<<6];
int cnt,tot,mn=INT_MAX,mx;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void kruskal(){
sort(e+1,e+1+m);
for (register int i=1;i<=n;++i) fa[i]=i;
for (register int i=1;i<=m;++i){
int fx=find(e[i].from),fy=find(e[i].to);
if (fx==fy) continue;
fa[fy]=fx,a[++tot]=e[i];
if (tot==n-1) break;
}
}
void update(int &p,int l,int r,int x){
if (!p) p=++cnt;tree[p]++;
if (l==r) return;
if (x<=mid) update(ls[p],l,mid,x);
else update(rs[p],mid+1,r,x);
}
int query(int l,int r,int L,int R,int p){
if (!p||L>R) return 0;
if (l>=L&&r<=R) return tree[p];
int res=0;
if (L<=mid) res+=query(l,mid,L,R,ls[p]);
if (R>mid) res+=query(mid+1,r,L,R,rs[p]);
return res;
}
vector<int>que[maxn];
int main(){
freopen("graph19.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d%d",&n,&m,&L);
for (register int i=1;i<=n;++i)
scanf("%d",c+i),
mn=min(mn,c[i]),
mx=max(mx,c[i]);
for (register int i=1;i<=m;++i)
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);
sort(e+1,e+1+m);
kruskal();
for (register int i=1;i<=n;++i){
fa[i]=i,size[i]=1;
update(root[i],mn,mx,c[i]);
que[i].push_back(i);
}
ll ans=0;
for (register int i=1;i<n;++i){
int x=find(a[i].from),y=find(a[i].to);
if (size[x]>size[y]) swap(x,y);
fa[x]=y,size[y]+=size[x];
ll res=0;
for (register int j=0;j<que[x].size();++j){
int pos=que[x][j];
res+=query(mn,mx,mn,c[pos]-L,root[y]);
res+=query(mn,mx,c[pos]+L,mx,root[y]);
if (!L) res-=query(mn,mx,c[pos],c[pos],root[y]);
}
ans+=res*a[i].val;
for (register int j=0;j<que[x].size();++j){
int pos=que[x][j];
update(root[y],mn,mx,c[pos]);
que[y].push_back(pos);
}
}
printf("%lld\n",ans);
return 0;
}


### naive 的游戏

#### 题目描述

1. 走到相邻的有桥相连的点上，因为上面有小怪，所以要消耗 1 的代价；
2. 使用技能跳一跳，跳到距离为 L 的点上，由于把该点上的小怪踩死了，所以不消耗代价。

type = 0

type = 1