cfRound933div3-E题解

E-Rudolf and k Bridges

题意:

选择的桥在连续的行中,每个桥的支架安装位置是可以不一样的.

做法：赛时也感觉也感觉是dp,但是害怕dp,就选择了逃避.往贪心方向想,认为每次到了每个跳板都要跳到最远距离,实际上这样是不行的.很明显,可能存在近一点的点花费更少。

实际上是dp,而且也不难。首先容易想到,需要一个前缀和,记录每个一行最少的花费的前缀和.然后枚举选择的连续的区间就好了。问题是每一行的最少花费怎么算。这其实是一个简单dp问题,对于一个普遍的点,他可能从他的前d+1个点来的,很明显,在前d+1个点中选花费最小那个就好了.如果每次都遍历前d+1个点, 找到到达那个点的最小值的话,这样复杂度很高。这个时候关键来了！用一个优先队列(小根堆)存放所有经历过的点的花费和下标,如果堆顶的点离现在的点超过d+1,直接pop.那么此时只要存在堆里的,都是合法范围的,而且堆顶必然是花费最小的,即从堆顶那个点跳到当前这个点即是最优的.然后把dp[i][m]加到前缀和,之后枚举区间,更新ans即可.

void solve(){               //E  跳板--是不对，到了某个点之后，不一定要跳尽，才是最好的;;
    // 求每一行最小的代价(dp)+前缀和
    //优先队列优化dp!!不用优先队列的话,因为每次需要前面合法的格子的最小代价是多少,需要遍历,这个时候就适合用优先队列,不用遍历去找最小代价.
    int n,m,k,d;   //n行,m列,建连续k桥,最大支架间隔d
    cin>>n>>m>>k>>d;
    vector<vector<int>> arr(n+1,vector<int>(m+1));
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    int pre[105]={0};
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;   //小根堆
        dp[i][1]=1,pq.emplace(1,1);
        for(int j=2;j<=m;j++){
            while(pq.size()&&pq.top().second+d+1<j) pq.pop();
            dp[i][j]=arr[i][j]+1+pq.top().first;
            pq.emplace(dp[i][j],j);
        }
    }
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+dp[i][m];
    //int ans=INT_MAX;            //INT_MAX不够大！！！！如果没有看错误样例,这里又要找错找很久很久都找不出来。。。经典错误！！
    int ans=LONG_LONG_MAX;
    for(int i=k;i<=n;i++) ans=min(ans,pre[i]-pre[i-k]);
    cout<<ans<<endl;
}

ps！！ans要初始化为LONG_LONG_MAX,因为INT_MAX不够大.经典细节.