目录
D - Gomamayo Sequence
题意是一个01字符串，把它变成只有一组相邻的0或相邻的1，改变每个字符都有一个代价
f1[i][0]表示从左到右把字符串变成01交错且第i个是0的最小代价
f2[i][0]表示从右到左把字符串变成01交错且第i个是0的最小代价
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
char s[N];
ll f1[N][2],f2[N][2];
int c[N];
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++){
for(int j=0;j<2;j++){
f1[i][j]=f1[i-1][j^1]+(s[i]==j+'0')*c[i];
}
}
for(int i=n;i>=1;i--){
for(int j=0;j<2;j++){
f2[i][j]=f2[i+1][j^1]+(s[i]==j+'0')*c[i];
}
}
ll ans=1e17;
for(int i=2;i<=n;i++){
ans=min(ans,f1[i-1][0]+f2[i][0]);
ans=min(ans,f1[i-1][1]+f2[i][1]);
}
cout<<ans<<'\n';
}
E - Minimize Sum of Distances
就是换根dp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long N=1e5+10,inf=1e18;
int n,c[N];
ll f[N],sum[N],res,ans;
vector<int>g[N];
//void dfs1(int u,int fa,int d){
// sum[u]=c[u];
// res+=1ll*d*c[u];
// for(auto v:g[u]){
// if(v==fa)continue;
// dfs1(v,u,d+1);
// sum[u]+=sum[v];
// }
//}
//void dfs2(int u,int fa){
// ans=min(ans,res);
// for(auto v:g[u]){
// if(v==fa)continue;
// res-=sum[v];
// res+=sum[1]-sum[v];
// dfs2(v,u);
// res+=sum[v];
// res-=sum[1]-sum[v];
// }
//}
void dfs1(int u,int fa,int d){
sum[u]=c[u];
f[1]+=1ll*d*c[u];
for(auto v:g[u]){
if(v==fa)continue;
dfs1(v,u,d+1);
sum[u]+=sum[v];
}
}
void dfs2(int u,int fa){
for(auto v:g[u]){
if(v==fa)continue;
f[v]=f[u]-2*sum[v]+sum[1];
dfs2(v,u);
}
}
int main(){
cin>>n;
ans=inf;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)cin>>c[i];
dfs1(1,0,0);
dfs2(1,0);
// cout<<ans<<'\n';
for(int i=1;i<=n;i++){
if(f[i]<ans)ans=f[i];
}cout<<ans;
}
思路：
一道非常典型的反悔贪心，反悔贪心就是我们需要建立一个贪心堆，先按照正常的思路（局部最优）进行贪心，如果当前取出的不是最优解，那就范湖
#include <bits/stdc++.h>
using namespace std;
const int N=4e+5;
bool mark[N];
int n,m,l[N],r[N],ans,a[N],tot;
struct node{
int id,v;
};
priority_queue<node>q;
bool operator<(const node &x,const node &y){
return x.v<y.v;
}
int main(){
cin>>n>>m;
if(m>n/2){
cout<<"Error!";return 0;
}
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<n;i++){
l[i]=i-1,r[i]=i+1; //创建环形链表
q.push({i,a[i]});//加入大根堆
}
l[1]=n;r[1]=2;l[n]=n-1;r[n]=1;//起点和尾点
q.push({1,a[1]});q.push({n,a[n]});
tot=n;
for(int i=1;i<=m;i++){
node cur;cur=q.top();q.pop();
if(mark[cur.id]){i--;continue;}//已经被删掉的点就跳过，注意i--，别又浪费了一袋
ans+=cur.v;//更新答案
a[++tot]=a[l[cur.id]]+a[r[cur.id]]-a[cur.id];//创建反悔点
q.push({tot,a[tot]});//反悔点入堆
l[tot]=l[l[cur.id]];r[tot]=r[r[cur.id]];//更新新节点的左右关系
r[l[l[cur.id]]]=tot;l[r[r[cur.id]]]=tot;//新节点的左右节点的指向新节点
mark[cur.id]=mark[l[cur.id]]=mark[r[cur.id]]=1;//删掉3个点
}
cout<<ans;
return 0;
}
