Problem M. Walking Plan(hdu 6331 分块 floyd)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6331
参考的这位童鞋的博客：https://blog.csdn.net/a1325136367/article/details/81317686
题意就是说：给你一个有向图然后 Q $Q$次询问，问从一点到另一点 至少 经过 K $K$ 条边的最短路

哇~这题真是学到了。。。还有这种操作~
这道题的基本思想就是：用 dp[k][i][j] $dp\left[k\right]\left[i\right]\left[j\right]$ 表示从 i $i$ 到 j $j$ 走 k $k$ 条路的最短路是多少
于是就有转移了： dp[k][i][j]=min(dp[k][i][j],dp[k−1][i][x]+Mp[x][j]) $dp\left[k\right]\left[i\right]\left[j\right]=min\left(dp\right[k\left]\right[i\left]\right[j],dp[k-1\left]\right[i\left]\right[x]+Mp[x\left]\right[j\left]\right)$，其中 x $x$ 就是随便的一个点
但是一个Floyd是 O(n3) $O\left(n^3\right)$，然后又是一层 K $K$ 的循环，就是 O(n3K) $O\left(n^{3}K\right)$， K $K$ 太大了，复杂度太高了

于是就有了分块这种操作。。。
分成 Dp[k][i][j] $Dp\left[k\right]\left[i\right]\left[j\right]$ 和 dp[k][i][j] $dp\left[k\right]\left[i\right]\left[j\right]$ ， Dp[k][i][j] $Dp\left[k\right]\left[i\right]\left[j\right]$就是每次 100 $100$ 步 100 $100$ 步的走

最后走 K $K$ 步的最短路就是 Dp[K100][i][j]+dp[K%100][i][j] $Dp\left[\frac{K}{100}\right]\left[i\right]\left[j\right]+dp\left[K\%100\right]\left[i\right]\left[j\right]$

但是我还不是很理解的一点是，为什么要要预处理到 K%100+n $K\%100+n$ 呢？然后问了哈博主才懂的T_T

就是说假如有 5 $5$ 个点嘛按次序弄成换，现在想问从 1 $1$ 走到 3 $3$ 走 k=1 $k=1$ 次的最短路，
但是要从 1 $1$ 走到 2 $2$ 最少都要 两次，怎么办喃？那就再多走一圈，相当于走 k=1+5=6 $k=1+5=6$ 次的，因为我们的 dp $dp$ 维护的是至少走 k $k$ 次，所以 dp[6] $dp\left[6\right]$ 取的是最短的 dp[2] $dp\left[2\right]$ 的值，所以这样就完美解决了~

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) ((long long)fac[(n)]*inv[(m)]%MOD*inv[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=55;
const int MOD=1e9+7;
const int inf=0x3f3f3f3f;
int Mp[maxn][maxn];
int dp[155][maxn][maxn];//小dp，只经过几十条边的 
int Dp[105][maxn][maxn];//大dp，经过几百几千条边的 
int main()
{
    int T,N,M,Q;
    cin>>T;
    while(T--)
    {
        memset(Mp,0x3f,sizeof Mp);
        memset(Dp,0x3f,sizeof Dp);
        memset(dp,0x3f,sizeof dp);
        cin>>N>>M;
        for(int i=1;i<=M;i++)
        {
            int t1,t2,v;
            scanf("%d%d%d",&t1,&t2,&v);
            Mp[t1][t2]=min(Mp[t1][t2],v);
        }
        for(int i=1;i<=N;i++)dp[0][i][i]=Dp[0][i][i]=0;


        //先把小dp处理出来
        for(int k=1;k<=150;k++)
        for(int l=1;l<=N;l++)
        for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
        {
            dp[k][i][j]=min(dp[k][i][j],dp[k-1][i][l]+Mp[l][j]);
        }

        //再把大dp处理出来 
        for(int k=1;k<=100;k++)
        for(int l=1;l<=N;l++)
        for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
        {
            Dp[k][i][j]=min(Dp[k][i][j],Dp[k-1][i][l]+dp[100][l][j]);//一口气就走100条边 
        }

        //以上求的是刚好经过k条边的最短路 
        //倒着来一遍求 至少 经过k条边的最短路 
        for(int k=150;k>=0;k--)//弄到150是因为有些不能从u到v，所以就多走一圈，而最大的一圈就是n=50 
        for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
        {
            dp[k][i][j]=min(dp[k][i][j],dp[k+1][i][j]);
        }

        cin>>Q;
        while(Q--)
        {
            int t1,t2,K;
            scanf("%d%d%d",&t1,&t2,&K);
            int ans=inf;
            int k1=K/100,k2=K%100;
            for(int i=1;i<=N;i++)ans=min(ans,Dp[k1][t1][i]+dp[k2][i][t2]);
            if(ans==inf)cout<<"-1\n";
            else cout<<ans<<endl;
        }
    }
}

Taotao Picks Apples

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6406

参考这位童鞋的博客：http://www.cnblogs.com/zzqc/p/9490772.html

思路：就是把他拆成 [1,pos−1] $[1,pos-1]$ 和 [pos+1,N] $[pos+1,N]$ ，然后在看修改的 pos $pos$ 这位的值能不能加到答案里面
维护答案的前缀 d1 $d1$ 和 d2 $d2$ ，后缀 d2 $d2$ 不好弄，所以用单调栈处理（我没想到，单调栈没用熟T_T）