轻功
题目描述
一共有 n 个木桩，要求从起点（0）开始，经过所有梅花桩，恰好到达终点 n,尊者神高达一共会 k 种门派的轻功，不同门派的轻功经过的梅花桩数不同，花费时间也不同。但是尊者神高达一次只能使用一种轻功，当他使用别的门派的轻功时，需要花费 W 秒切换（开始时可以是任意门派,不需要更换时间）。由于尊者神高达手残，所以经过某些梅花桩（包括起点和终点）时他不能使用一些门派的轻功。尊者神高达想知道他最快多久能到达终点。如果无解，则输出-1。
思路
我们可以写一个 $O(nk)$ 的 DP。$f_{i,j}$ 表示经过第 $i$ 个梅花桩结束使用门派 $j$，那么它可以从 $f_{i-cost_j,p}$ 转移过来。发现 $p$ 的具体数值对转移没有影响，只需要特判 $p==j$ 的情况，所以处理 $f_{i,p}$ 的最小值，O(1) 转移。限制条件只需要前缀和判断即可。
代码
#include
#define inf 0x77777777
#define ll long long
#define maxn 510
using namespace std;
int n,k,W,Q;
int a[maxn],v[maxn];
ll f[maxn][maxn],s[maxn][maxn];
ll ans=inf;
int main(){
freopen("qinggong.in","r",stdin);
freopen("qinggong.out","w",stdout);
scanf("%d%d%d",&n,&k,&W);
for (int i=1;i<=k;i++)
scanf("%d%d",a+i,v+i);
scanf("%d",&Q);
for (int i=1,xi,ki;i<=Q;i++)
scanf("%d%d",&xi,&ki),
s[xi][ki]++;
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)
s[i][j]+=s[i-1][j];
memset(f,inf,sizeof(f));
for (int i=0;i<=k;i++)
f[0][i]=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=k;j++){
if (a[j]<=i&&s[i][j]-s[max(i-a[j]-1,0)][j]==0){
f[i][j]=min(f[i][j],f[i-a[j]][j]+v[j]);
f[i][j]=min(f[i][j],f[i-a[j]][0]+v[j]+W);
f[i][0]=min(f[i][0],f[i][j]);
}
}
}
for (int i=1;i<=k;i++)
ans=min(ans,f[n][i]);
printf("%lld",ans==inf?-1:ans);
} 开荒
题目描述
(太长了以下是我的精简版)
给定一棵树，点有权值，支持修改。询问某 $k$ 个点的最小联通块权值和。
思路
首先我们不考虑修改，如何计算答案。发现将 $k$ 个点按 $DFS$ 序升序以后，点 $i$ 到自己和前一个点 $i-1$ 的最近公共祖先深度一定递增，并且到 $LCA$ 的路径的集合就是最小联通块，注意第一个点要和所有点的 $LCA$ 相连。将点权转移到连接父亲的边上，计算答案的时候可以做到不重复，但是会遗漏所有点的 $LCA$，单独计入即可。
代码
#include
#define ll long long
#define maxn 1000100
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn<<1];
int head[maxn],w[maxn],cnt,ind;
int dfn[maxn<<2],tag[maxn][2];
int dep[maxn],lca[maxn<<1][21];
int n,q;
ll dis[maxn];
void Add(int x,int y){
l[++cnt]=Edge(y,head[x]);
head[x]=cnt;
}
struct Bt{
ll t[maxn<<1];
void add(int x,int y){
while(x<=ind){
t[x]+=y;
x+=(x&-x);
}
}
ll sum(int x){
ll r=0;
while(x){
r+=t[x];
x-=(x&-x);
}
return r;
}
}pat;
void dfs(int u,int f){
dis[u]=dis[f]+w[u],dep[u]=dep[f]+1;
dfn[++ind]=u,tag[u][0]=ind;
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
dfs(v,u);
dfn[++ind]=u;
}
tag[u][1]=ind;
}
void init(){
for (int i=1;i<=ind;i++)
lca[i][0]=dfn[i];
for (int j=1;j<21;j++){
for (int i=1;i<=ind;i++){
if (i+(1<r) swap(l,r);
int k=log(r-l+1.0)/log(2.0);
if (dep[lca[l][k]] 跑商
题目描述
给定一个 $n$ 个点，$m$ 条边的简单无向图，支持修改点权。每次询问路径上点权最小值。