BZOJ2165:大楼 倍增+dp

题目大意:自己看

思路:

首先利用倍增预处理出\(f_{i,j,k}\)表示从\(i\)开始到达\(j\)走了\(2^k\)步的上升的最大高度.

我们不断倍增直到从1开始的某个终点的最大高度大于\(m\).

最终计算答案时,我们从高到低枚举每个二进制位\(p\),若当前状态再转移\(2^p\)步之后从\(1\)开始的最大上升高度依旧不能达到\(m\)的话,我们就令答案加上\(2^p\),同时更新当前状态.

这样最终答案要加上1,由于我们每次只是当不够\(m\)时才加上,所以目前答案比真正答案少\(1\).

(我的程序在Tsinsen上AC,在BZOJ上TLE)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 110
LL f[N][N][61],now[N][N],g[N][N];
 
int main(){
    int T;scanf("%d",&T);
    register int i,j,k;
     
    int n;LL total,t;
    while(T--){
        scanf("%d%lld",&n,&total);
        memset(f,0xc0,sizeof f);
        for(i=1;i<=n;++i)for(j=1;j<=n;++j){
            scanf("%lld",&t);
            if(t)f[i][j][0]=t;
        }
        int Maxins;
        LL tmp;
        for(int d=1;;++d){
            for(i=1;i<=n;++i)
                for(j=1;j<=n;++j)
                    for(k=1;k<=n;++k)
                        tmp=f[i][k][d-1]+f[k][j][d-1],f[i][j][d]=f[i][j][d]<tmp?tmp:f[i][j][d];
            bool find=0;
            for(j=1;j<=n;++j)if(f[1][j][d]>=total)find=1;
            if(find){Maxins=d;break;}
        }
         
        LL res=0;
        memset(now,0,sizeof now);
        for(int d=Maxins;d>=0;--d){
            for(i=1;i<=n;++i){
                for(j=1;j<=n;++j){
                    g[i][j]=-1LL<<60;
                    for(k=1;k<=n;++k)
                        tmp=f[i][k][d]+now[k][j],g[i][j]=g[i][j]<tmp?tmp:g[i][j];
                }
            }
            bool find=0;
            for(j=1;j<=n;++j)if(g[1][j]>=total)find=1;
            if(!find){
                for(i=1;i<=n;++i)
                    for(j=1;j<=n;++j)
                        now[i][j]=g[i][j];
                res+=1LL<<d;
            }
        }
         
        cout<<res+1<<endl;
    }
     
    return 0;
}