ARC085F(动态规划,线段树)
2024-08-29 09:17:46
#include<bits/stdc++.h>
using namespace std;
const int maxn = 0x3f3f3f3f;
int mn[801000];
int cost[200100];
int dp[200100];
vector<int>v[200100];
void add_edge(int l,int r,int root){
if(l==r){
mn[root]=maxn;//叶子节点
return ;
}
int mid=(l+r)/2;
add_edge(l,mid,root<<1);//递归构造左子树
add_edge(mid+1,r,(root<<1)+1);//递归构造右子树
mn[root]=min(mn[root<<1],mn[(root<<1)+1]);//根据左右子树根节点的值,更新当前根节点的值
}
int query(int left,int right,int l,int r,int root){//区间查找,l和r表示当前区间端点,left和right表示查询区间端点
if(left<=l&&r<=right)//当前节点区间包含在查询区间内
return mn[root];
int mid=(l+r)/2;
int res=maxn;
if(left<=mid)
res=min(res,query(left,right,l,mid,root<<1));//分别从左右子树查询,返回两者查询结果的较小值
if(right>mid)
res=min(res,query(left,right,mid+1,r,(root<<1)+1));
return res;
}
void update(int pos/*待更新节点的标*/,int val/*更新的值*/,int l,int r,int root){//当前区间的端点
if(l==r){
mn[root]=min(mn[root],val);//找到了相应的节点,更新(这里更新的是叶子节点,会对父节点产生影响)
return;
}
int mid=(l+r)/2;
if(pos<=mid)
update(pos,val,l,mid,root<<1);//在左子树中更新
else
update(pos,val,mid+1,r,(root<<1)+1);//在右子树中更新
mn[root]=min(mn[root<<1],mn[(root<<1)+1]);//根据左右子树的值回溯更新当前节点的值
}
int main(){
int n,q;
int cnt=0;
scanf("%d",&n);
add_edge(1,n,1);
for(int i=1,j;i<=n;i++){
scanf("%d",&j);
cnt+=!j;//b中0的个数
cost[i]=j?1:-1;//当前bi为1即为1,bi为0即为-1,在加和前x位时即可得到bi为1的数量减去bi为零的数量
}
scanf("%d",&q);
for(int i=0,j,k;i<q;i++){
scanf("%d%d",&j,&k);
v[j].push_back(k);//存下区间
}
memset(dp,maxn,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
int ct = v[i].size();//左端点为i的区间的个数
for (int k = 0; k < ct;k++){
int j=v[i][k];//右端点
int tmp=dp[i-1];
tmp=min(tmp,query(max(i-1,1)/*i为1时仍为1,其他为i-1*/,j,1,n,1));
if(tmp<dp[j]){//存在更优解
dp[j]=tmp;
update(j,tmp,1,n,1);
}
}
dp[i]=min(dp[i],dp[i-1]+cost[i]);//cost[i]为1表示b[i]=1,cost[i]为-1表示b[i]=0,由于dp[i]表示a0b1-a0b0
}
printf("%d\n",dp[n]+cnt);//cnt表示b0的数量
return 0;
}
/*题目要求求min{(a=0&&b=1)+(a=1&&b=0)},即求min{(a=0&&b=1)+(b=0)-(a=0&&b=0)},
即求b=0+min{(a=0&&b=1)-(a=0&&b=0)},dp[i]表示前i个数的min{(a=0&&b=1)-(a=0&&b=0)}*/
/*线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题
附上结构体区间更新的细节讲解http://www.cnblogs.com/TenosDoIt/p/3453089.html*/
using namespace std;
const int maxn = 0x3f3f3f3f;
int mn[801000];
int cost[200100];
int dp[200100];
vector<int>v[200100];
void add_edge(int l,int r,int root){
if(l==r){
mn[root]=maxn;//叶子节点
return ;
}
int mid=(l+r)/2;
add_edge(l,mid,root<<1);//递归构造左子树
add_edge(mid+1,r,(root<<1)+1);//递归构造右子树
mn[root]=min(mn[root<<1],mn[(root<<1)+1]);//根据左右子树根节点的值,更新当前根节点的值
}
int query(int left,int right,int l,int r,int root){//区间查找,l和r表示当前区间端点,left和right表示查询区间端点
if(left<=l&&r<=right)//当前节点区间包含在查询区间内
return mn[root];
int mid=(l+r)/2;
int res=maxn;
if(left<=mid)
res=min(res,query(left,right,l,mid,root<<1));//分别从左右子树查询,返回两者查询结果的较小值
if(right>mid)
res=min(res,query(left,right,mid+1,r,(root<<1)+1));
return res;
}
void update(int pos/*待更新节点的标*/,int val/*更新的值*/,int l,int r,int root){//当前区间的端点
if(l==r){
mn[root]=min(mn[root],val);//找到了相应的节点,更新(这里更新的是叶子节点,会对父节点产生影响)
return;
}
int mid=(l+r)/2;
if(pos<=mid)
update(pos,val,l,mid,root<<1);//在左子树中更新
else
update(pos,val,mid+1,r,(root<<1)+1);//在右子树中更新
mn[root]=min(mn[root<<1],mn[(root<<1)+1]);//根据左右子树的值回溯更新当前节点的值
}
int main(){
int n,q;
int cnt=0;
scanf("%d",&n);
add_edge(1,n,1);
for(int i=1,j;i<=n;i++){
scanf("%d",&j);
cnt+=!j;//b中0的个数
cost[i]=j?1:-1;//当前bi为1即为1,bi为0即为-1,在加和前x位时即可得到bi为1的数量减去bi为零的数量
}
scanf("%d",&q);
for(int i=0,j,k;i<q;i++){
scanf("%d%d",&j,&k);
v[j].push_back(k);//存下区间
}
memset(dp,maxn,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
int ct = v[i].size();//左端点为i的区间的个数
for (int k = 0; k < ct;k++){
int j=v[i][k];//右端点
int tmp=dp[i-1];
tmp=min(tmp,query(max(i-1,1)/*i为1时仍为1,其他为i-1*/,j,1,n,1));
if(tmp<dp[j]){//存在更优解
dp[j]=tmp;
update(j,tmp,1,n,1);
}
}
dp[i]=min(dp[i],dp[i-1]+cost[i]);//cost[i]为1表示b[i]=1,cost[i]为-1表示b[i]=0,由于dp[i]表示a0b1-a0b0
}
printf("%d\n",dp[n]+cnt);//cnt表示b0的数量
return 0;
}
/*题目要求求min{(a=0&&b=1)+(a=1&&b=0)},即求min{(a=0&&b=1)+(b=0)-(a=0&&b=0)},
即求b=0+min{(a=0&&b=1)-(a=0&&b=0)},dp[i]表示前i个数的min{(a=0&&b=1)-(a=0&&b=0)}*/
/*线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题
附上结构体区间更新的细节讲解http://www.cnblogs.com/TenosDoIt/p/3453089.html*/
最新文章
- Scrapy003-项目流程
- 日志:using the Connector/J connection property &#39;autoReconnect=true&#39; to avoid this problem
- mysql解压缩安装(一)
- 好无语的问题----include 后面需要空格么?
- 使用Eclipse创建maven项目
- 【Java】IO流简单分辨
- POJ_1088 滑雪(记忆型DP+DFS)
- Objective-C 字典、可变字典
- Oracle EBS Web ADI 中的术语
- hdu3072
- jmeter对http协议中post请求接口测试
- 最新 Zookeeper + Flume + Kafka 简易整合教程
- Python协程的引入与原理分析
- GitLab 社区版 11.0.2用户管理教程
- Xamarin 简化的Android密钥库签名
- mysql中关于关联索引的问题——对a,b,c三个字段建立联合索引,那么查询时使用其中的2个作为查询条件,是否还会走索引?
- OpenStack 安装:keystone服务
- babel-preset-env使用介绍
- wpf中通过ObjectDataProvider实现文本框的双向数据绑定(ps:适用于在文本框比较多的时候使用)
- Python 列表推导实例
热门文章
- Codeforces 180C Letter:dp
- 英语发音规则---th
- 使用jquery执行ajax
- log4j No appenders could be found for logger
- 【leetcode刷题笔记】Populating Next Right Pointers in Each Node II
- 2017-2018-1 20179215《Linux内核原理与分析》第三周作业
- 【转】Pro Android学习笔记(四六):Dialog(3):对话框弹对话框
- myeclipse保存时弹出Building workspace
- linux日常管理-rsync后台服务方式-2
- vue的安装配置