E. Rudolf and k Bridges-Codeforces Round 933 (Div. 3)

这道题需要使用到deque
deque:双端队列，可以在前后存取元素。
题目要求连续造k座桥，那么只需要把每一座桥的建造成本记录一下，最后取其中和最小的连续k座桥的成本即可。
对于每一座桥计算他的建造成本：
用dp来做，这座桥的第j个位置的建造成本为dp[j];
dp[j]=dp[k]+a[i][j]+1;其中k是一个范围[j-k-1,j-1]；
最后就是一个前缀和来求连续k座桥的成本了。

#include<iostream>
#include<deque>
#include<vector>
#define int long long
using namespace std;
void solve(){int n,m,k,d;cin>>n>>m>>k>>d;int a[n+2][m+2];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}vector<int>ans;for(int i=1;i<=n;i++){deque<int>Q;//记录的是序号下标int dp[m+2];dp[1]=1;Q.push_back(1);for(int j=2;j<=m;j++){if(!Q.empty()&&j-Q.front()-1>d) Q.pop_front();//间距超出范围，出列dp[j]=dp[Q.front()]+a[i][j]+1;while(!Q.empty()&&dp[Q.back()]>dp[j]) Q.pop_back();//后面的比新来的j的成本还要更大，这些数直接不要了Q.push_back(j);//新来的j入队}ans.push_back(dp[m]);}int pre[n+2];pre[0]=ans[0];for(int i=1;i<ans.size();i++){pre[i]=pre[i-1]+ans[i];}int aans=pre[k-1];for(int i=k;i<ans.size();i++){aans=min(aans,pre[i]-pre[i-k]);}cout<<aans<<endl;
}
signed main(){int T;cin>>T;while(T--){solve();}
}