F1. Cycling (Easy Version)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define int long longconst int N=5010;
int n;int a[N];int f[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)f[i]=INF;
f[0]=0;
for(int i=1;i<=n;i++){int mx=i;for(int j=i;j>=1;j--){if(a[j]<a[mx])mx=j;f[i]=min(f[i],f[j-1]+i-mx+i-j+a[mx]*(i-j+1));}
}
cout<<f[n]<<'\n';}
signed main(){std::ios::sync_with_stdio(false);int T=1;cin>>T;while(T--){solve();}
}
B. Gellyfish and Baby's Breath
签到
cf786B B. Legacy
线段树优化建图板子
线段树的结点作为图的点，建树，出树儿子向父亲，入树父亲向儿子。两树的叶子结点相连
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f#define int long longconst int N = 100010;
int n, q, s; int lf[N];
vector<pii> G[2 * 4 *N];
int d[2 * 4 * N];
struct Tree{int l,r;
}tr[4*N];
void bui(int u, int l, int r){tr[u] = {l, r};if(l == r){lf[l] = u;//存叶子return ;}//出树，儿子向父亲G[u * 2 + 4 * n].pb({u + 4 * n, 0});G[u * 2 + 1 + 4 * n].pb({u + 4 * n,0});//入树，父亲向儿子G[u].pb({u * 2, 0});G[u].pb({u * 2 + 1, 0});int mid = (l + r) >> 1;bui(u*2, l, mid);bui(u*2 + 1, mid + 1, r);
}void query(int u, int x, int y, int v, int w, int rev){if(x <= tr[u].l && tr[u].r <= y){//出树向入树if(rev == 0) G[v + 4*n].pb({u, w});else G[u + 4*n].pb({v,w});return ;}int mid = (tr[u].l + tr[u].r) >> 1;if(x <= mid) query(u << 1, x, y, v, w, rev);if(y >= mid + 1)query(u << 1 | 1, x, y, v, w, rev);
}void dijk(){priority_queue<pii, vector<pii>, greater<pii> > pq;for(int i = 1; i <= 4*n + 4*n; i ++) d[i] = INF;d[lf[s]] = 0; pq.push({0, lf[s]});while(!pq.empty()){auto [_, u] = pq.top(); pq.pop();for(auto [v,w] : G[u]){if(d[v] > d[u] + w){d[v] = d[u] + w;pq.push({d[v], v});}}}}void solve(){cin >> n >> q >> s;bui(1, 1, n);for(int i = 1; i <= n; i ++){G[lf[i]].pb({lf[i] + 4*n, 0});G[lf[i] + 4*n].pb({lf[i], 0});}while(q --){int op; cin >> op;if(op == 1){int v, u, w; cin >> v >> u >> w;G[lf[v]].pb({lf[u], w});}else if(op == 2){int v, l, r, w; cin >> v >> l >> r >> w;query(1, l, r, lf[v], w, 0); }else {int v, l, r, w; cin >> v >> l >> r >> w;query(1, l, r, lf[v], w, 1);}}dijk();for(int i = 1; i <= n; i ++){if(d[lf[i]] > INF / 2) cout << -1 << ' ';else cout << d[lf[i]] << ' ';} cout << '\n';}
signed main(){std::ios::sync_with_stdio(false);int T = 1; // cin >> T;while(T--){solve();}
}