F. Wi-Fi(线段树实现dp)
2024-09-07 01:31:56
题:http://codeforces.com/contest/1216/problem/F
dp[i][0]:表示第i个位置不装的最小代价
dp[i][1]:表示第i个位置装的最小代价
T1的线段树是维护装的最小代价
T2的线段树是维护装和不装的最小代价
#include<bits/stdc++.h>
using namespace std;
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
typedef long long ll;
const int M=2e5+;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll dp[M][];
char s[M];
struct node{
ll tree[M<<];
T(){memset(tree,INF,sizeof(tree));}
void up(int root){
tree[root]=min(tree[root<<],tree[root<<|]);
}
void update(int pos,ll val,int root,int l,int r){
if(l==r){
tree[root]=min(tree[root],val);
return ;
}
int midd=(l+r)>>;
if(pos<=midd)
update(pos,val,lson);
else
update(pos,val,rson);
up(root);
}
ll query(int L,int R,int root,int l,int r){
if(L<=l&&r<=R){
return tree[root];
}
int midd=(l+r)>>;
ll ans=INF;
if(L<=midd)
ans=min(ans,query(L,R,lson));
if(R>midd)
ans=min(ans,query(L,R,rson));
return ans;
}
}T1,T2;
int main(){
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s+);
memset(dp,INF,sizeof(dp));
memset(T1.tree,INF,sizeof(T1.tree));
memset(T2.tree,INF,sizeof(T2.tree));
dp[][]=dp[][]=;
// cout<<dp[2][1]<<endl;
T2.update(,,,,n);
for(int i=;i<=n+;i++){
dp[i][]=T1.query(max(,i-k),i-,,,n);
if(s[i]=='')
dp[i][]=T2.query(max(,i-k-),i-,,,n)+i-;
else
dp[i][]=min(min(dp[i-][],dp[i-][]),T1.query(max(,i-k-),i-,,,n))+i-;
T2.update(i,min(dp[i][],dp[i][]),,,n);
if(s[i]=='')
T1.update(i,dp[i][],,,n);
}
printf("%I64d\n",min(dp[n+][],dp[n+][]));
return ;
}
最新文章
- flask 链接 url_for()
- jquery checkbox 复选框多次点击判断选中状态,以及全选/取消的代码示例
- 使用VS2013在WIN8.1上运行gaclib的hello world
- iOS打包导出时出现Missing iOS Distribution signing
- datatable把一个LIst的数据放入两个colum防止窜行的做法
- Bug:java.lang.IllegalStateException
- 【HDOJ】4322 Candy
- poj 1821 Fence 单调队列优化dp
- 25 读取jar包内log4j.properties文件方法
- 【转载】如何让Chrome浏览器允许本地环境支持Ajax
- javascript 值传递
- C语言——第0次作业(二)
- SPRINT四则运算(第二天)
- Codeforces-542div2
- Fis3构建迁移Webpack之路
- OpenNebula学习第二节OpenNebula Node Installation
- 【Linux】分割命令split
- SQL (FMDB)
- J2EE的体系架构
- 条件随机场(Conditional random field,CRF)