题意：
给定n个房间 要给每个房间连上网络 第i个房间连上网络的花费为i 有些房间可以装上路由器 如果装上路由器 那么左边k个和右边k个都可以被装上网络 且装路由器的费用也为i
问最少花费使得所有的房间装上网络
dp 单调栈 ：
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
const int N=2e6+10;
int n,m,l,r,st[N],k;
char s[N];
ll dp[N];
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",s+1);
l=r=1;st[1]=0;
rep(i,1,n+k)
{
dp[i]=dp[i-1]+i;
if(i>k&&s[i-k]=='1')
{
dp[i]=min(dp[i],dp[st[l]]+i-k);
}
if(st[l]<i-2*k)l++;
while(l<=r&&dp[st[r]]>=dp[i])r--;
st[++r]=i;
}
ll ans=1e18;
rep(i,n,n+k)ans=min(ans,dp[i]);
cout<<ans;
return 0;
}比赛的时候做法是最短路
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define inf 0x3f3f3f3f
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
const int N=1e6;
const int M=1e6;
int head[M];
int pos;
struct Edge
{
ll v;int to,nex;
}edge[M];
void add(int a,int b,ll c)
{
edge[++pos]=Edge{c,b,head[a]};
head[a]=pos;
}
struct Node
{
ll d;int id;
bool operator<(const Node& b)const
{
return d>b.d;
}
};
ll dis[N];
int vis[N];
int n,m,k,a,b,c,t;
char s[N];
void dijkstra(int s)
{
rep(i,0,n+1)dis[i]=1e18;
dis[s]=0;
priority_queue<Node>q;
q.push(Node{0,s});
while(!q.empty())
{
Node u=q.top();q.pop();
if(vis[u.id])continue;
vis[u.id]=1;
for(int i=head[u.id];i;i=edge[i].nex)
{
int v=edge[i].to;
if(u.d+edge[i].v<dis[v])
{
dis[v]=u.d+edge[i].v;
q.push(Node{dis[v],v});
}
}
}
}
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",s+1);
rep(i,1,n)
{
add(i,i+1,1ll*i);
add(i,i-1,1ll*0);
if(s[i]=='1')
add( max(1,i-k), min( n+1,i+k+1 ), 1ll*i );
}
add(n+1,n,1ll*0);
dijkstra(1);
cout<<dis[n+1];
return 0;
}