首页 > 其他分享 >一个题

一个题

时间:2024-01-28 23:33:07浏览次数:24  
标签:ch 一个 pos long 花费 include define

http://zhengruioi.com/contest/1537/problem/2825

一共只有两次操作机会,那么最后一次我们肯定选择所有 \(p_i\not=i\)。

先假设所有点都在第二次操作(花费 \(b_i\)),然后,考虑在第一次操作提前将某些球归位(使得 \(p_i=i\))。

如果要归位球 \(i\),设 \(pos_i\) 为放置球 \(i\) 的盒子的编号,则我们要操作 \(pos_i,i\),花费 \(a_{pos_i}+a_i\),第二次操作少花费 \(b_i\)。

但此时有一个特殊情况。将所有 \(i\) 向 \(pos_i\) 连边,则若选择一个整个的环,花费 \(\sum a_i\),第二次操作少花费 \(\sum b_i\)。将环压到一个序列里(\(a_{i-1}\) 为 \(pos_i\))做环形 dp,设 \(f_{i,0/1}\) 为考虑前 \(i\) 个位置,当前状态为选/不选的最优方案,转移方程 \(f_{i,0}=\max(f_{i-1,0},f_{i-1,1}),f_{i,1}=\max(f{i-1,0}+a_i,f_{i-1,1}+a_i-b_{i-1})\)。

再考虑成环的情况,强制首尾都选,再做一遍 dp 即可。

点击查看代码
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define FlushIn fread(Fread::ibuf,1,1<<21,stdin)
#define FlushOut fwrite(Fwrite::obuf,1,Fwrite::S-Fwrite::obuf,stdout)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=d)
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
#define int long long
//#define int __int128
using namespace std;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
bool smallingll(long long x,long long y){return x<y;}
namespace Fread {
	const int SIZE=1<<21;
	char ibuf[SIZE],*S,*T;
	inline char getc(){if(S==T){T=(S=ibuf)+fread(ibuf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite{
	const int SIZE=1<<21;
	char obuf[SIZE],*S=obuf,*T=obuf+SIZE;
	inline void flush(){fwrite(obuf,1,S-obuf,stdout);S=obuf;}
	inline void putc(char c){*S++=c;if(S==T)flush();}
	struct NTR{~NTR(){flush();}}ztr;
}
/*#ifdef ONLINE_JUDGE
#define getchar Fread::getc
#define putchar Fwrite::putc
#endif*/
inline int rd(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[40];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=1e5+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,c[maxn],d[maxn];
int p[maxn];//出边 
int pos[maxn];//入边 
bool vis[maxn];
int ans;
int a[maxn],m;
void search(int x){a[++m]=x,vis[x]=1;if(!vis[pos[x]])search(pos[x]);}
//先处理不成环的情况,在强制钦定首尾相连
//若不成环的情况成了环,则不优/已被计算过 
int f[maxn][2];
void init(){
	rep(i,1,m)f[i][0]=f[i][1]=llinf;
}
int dp(){
	int sum=0,res=0;
	rep(i,1,m)sum+=c[a[i]]-d[a[i]];
	res=min(res,sum);
	//不成环
	init(); 
	f[1][0]=0,f[1][1]=c[a[1]];
	rep(i,2,m){
		f[i][0]=min(f[i-1][0],f[i-1][1]);
		f[i][1]=min(f[i-1][0]+c[a[i]],f[i-1][1]+c[a[i]]-d[a[i-1]]);
	}
	res=min({res,f[m][0],f[m][1]});
	//强制成环
	init();
	f[1][1]=c[a[1]]-d[a[m]];
	rep(i,2,m){
		f[i][0]=min(f[i-1][0],f[i-1][1]);
		f[i][1]=min(f[i-1][0],f[i-1][1]-d[a[i-1]])+c[a[i]];
	}
	res=min(res,f[m][1]);
	return res;
}
void solve_the_problem(){
	n=rd();
	rep(i,1,n)p[i]=rd(),pos[p[i]]=i;
	rep(i,1,n)c[i]=rd();
	rep(i,1,n)d[i]=rd(),ans+=d[i];
	rep(_,1,n)if(!vis[_]){
		m=0,search(_);
		if(m==1)ans-=d[_];else ans+=dp();
	}
	write(ans);
}
bool Med;
signed main(){
//	freopen(".in","r",stdin);freopen(".out","w",stdout);
//	fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
	int _=1;while(_--)solve_the_problem();
}
/*

*/

标签:ch,一个,pos,long,花费,include,define
From: https://www.cnblogs.com/dcytrl/p/17993630

相关文章

  • 实现一个状态机
    问题的描述最近在改仿真软件的状态切换,什么意思呢,这东西有点像个播放器,但是不仅仅是播放暂停那么简单。首先我们画一个图,以一个图说明:  通过以前的面向对象设计经验我们知道有一种叫状态机的东西,简而言之就是把每个状态通过节点对象包装,节点是什么类型就是当前处于什么状态,......
  • 用Java语言实现一个观察者模式
    观察者模式(也被称为发布/订阅模式),提供了避免组件之间紧密耦合的另一种方法,它将观察者和被观察的对象分开。在该模式中,一个对象通过添加一个方法(该方法允许另一个对象,即观察者注册自己)使本身变得可观察。当可观察的对象更改时,它会将消息发送到已注册的观察者。这些观察者收到消......
  • 基于Basic auth 的一个C# 示例
    最近在做公司的一个项目时,客户需要我们定时获取他们矩阵系统的数据。在与客户进行对接时,提到他们的接口使用的目前不常用的BASIC认证。天呢,它好不安全,容易被不法人监听,咋还在使用呀。但是没办法呀,谁让客户的系统就是这样的呢。因为现在开发中绝大多数使用的是基于Bearer认证的。......
  • 如何管理好一个一盘散沙的新团队?
    如何管理好一个一盘散沙的新团队?**面对这样一道大题:很多人都在谈人,但缺少事人是管不住的;很多人都只关心方法,但真正能让80%的人通过80%的努力达到80分的不是方法,而是方法论!**如何盘活并管理好一个一盘散沙的新团队?或许“六步走”的方法论,才能帮助局中人找到捉刀的正确思路与姿势。......
  • 生成一个满二叉数算法
    1、树结构类publicclassTreeNode<T>{Tval;TreeNode<T>parent;TreeNode<T>right;TreeNode<T>left;publicTreeNode(){}publicTreeNode(Tval){this.val=val;this.parent=nul......
  • 使用伪元素为dom元素写一个蒙层
    把下方css样式复制给任一元素,修改宽高属性即可增加蒙层<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><linkrel=&qu......
  • Tornado 输出第一个"hello world"
    在Python中,使用Tornado框架输出"HelloWorld"的示例代码如下:importtornado.ioloopimporttornado.webclassMainHandler(tornado.web.RequestHandler):defget(self):self.write("HelloWorld")defmake_app():returntorna......
  • 电脑和打印机在同一个网络却无法打印?
    年底忙着交付一个云电脑项目,又忙着要三年前做的医院项目工程款,着实有些头疼,所以好久没更新了,趁着今天有空,来更新一篇文章吧。电脑和打印机在同一个网络内,却无法打印,这个客户也挺最艰难的,资金遇到问题,暂时居家办公了,能帮就帮一吧。故障现象:打印机连接网线后,还是无法打印。看打印机的......
  • C语言代码实现:一个整数存储在内存中的二进制中的1的个数
    e.g.代码实现:一个整数存储在内存中的二进制中的1的个数#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ intnum=0; intcount=0; printf("统计num的补码中有几个1,请输入num:>"); scanf("%d",&num); //统计num的补码中有几个1 //法一 //while(nu......
  • 创建onepose虚拟环境时一个看似复杂的报错的解决
    这个错误看似先是mdl不应该为None,但是实际却为None,但是后面有一句:在处理这个异常时,出现了另一个异常当出现这个情况时,实际上应该先处理后面这个异常,这个是gpt告诉我的(见下图):后面这个异常报的是libcublas.so.11有问题,看似和我之前建立pixel-perfect-sfm的conda虚拟环境时ln-......