题: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 ;
}

最新文章

  1. flask 链接 url_for()
  2. jquery checkbox 复选框多次点击判断选中状态,以及全选/取消的代码示例
  3. 使用VS2013在WIN8.1上运行gaclib的hello world
  4. iOS打包导出时出现Missing iOS Distribution signing
  5. datatable把一个LIst的数据放入两个colum防止窜行的做法
  6. Bug:java.lang.IllegalStateException
  7. 【HDOJ】4322 Candy
  8. poj 1821 Fence 单调队列优化dp
  9. 25 读取jar包内log4j.properties文件方法
  10. 【转载】如何让Chrome浏览器允许本地环境支持Ajax
  11. javascript 值传递
  12. C语言——第0次作业(二)
  13. SPRINT四则运算(第二天)
  14. Codeforces-542div2
  15. Fis3构建迁移Webpack之路
  16. OpenNebula学习第二节OpenNebula Node Installation
  17. 【Linux】分割命令split
  18. SQL (FMDB)
  19. J2EE的体系架构
  20. 条件随机场(Conditional random field,CRF)

热门文章

  1. markdown使用介绍
  2. Java 跨系统开发隐患(一)
  3. jdk 的安装教程
  4. Cavace 自定义View绘制
  5. hdu1312题解
  6. tomcat8.5的安装、卸载、配置和部署
  7. C++ 11新标准实现POJ No.2195-GoingHome
  8. 移除手机端a标签点击自动出现的边框和背景
  9. 《Docekr入门学习篇》——Docker实战
  10. tensorflow模型