LA5106: Let the light guide us

Dp·樹狀數組

題解：

裸方程：

當 |j−k|<=magic[i−1][k]+magic[i][j] 時，

f[i][j]=min{f[i−1][k]}+cost[i][j]

時間複雜度： O(nm2) .

優化一下。像這種有絕對值的一定是規定大小，把絕對值去掉，然後正反做兩遍。

k<=j，k−magic[i−1][k]<=j+magic[i][j]

然後用bit維護最小值即可。詳見代碼。

時間複雜度： O(nmlogm) .

說一下我犯的zz錯誤：

1.先正着跑完所有行在反着跑所有行。。。

2.reverse沒寫足，有的沒reverse回來。。。

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
//#define debug
#ifdef debug
    #define D(x) cout<<#x<<" = "<<x<<"  "
    #define E cout<<endl
#else
    #define D(x)
    #define E
#endif
using namespace std;
const int N = ;
const int mxn = ;
const int INF = ;

int n,m,cost[][N],magic[][N],f[N],g[N],res[N],ans; 

struct BIT{
    int c[mxn+], sz;
    void init(int _sz){ sz=_sz; memset(c,,sizeof(c)); }
    void ins(int x,int d){ if(x<)x=; while(x<=sz){ c[x]=min(c[x],d); x+=x&(-x); } }
    void clear(int x){ if(x<)x=; while(x<=sz){ c[x]=INF; x+=x&(-x); } }
    int mn(int x){ int ans=INF; while(x>){ ans=min(ans,c[x]); x-=x&(-x); } return ans; }
} bit;


void dp(int i,int f[N]){
//  printf("dp: \n");
    for(int j=m;j>=;j--){
        D(i); D(j); E;
//      printf("ins: pos=%d  d=%d\n",j-magic[i-1][j],res[j]);
        bit.ins(j-magic[i-][j],res[j]);
        D(j+magic[i][j]); D(bit.mn(j+magic[i][j])); E;
        f[j]=bit.mn(j+magic[i][j])+cost[i][j];
        D(f[j]); E;
    }
    for(int j=;j<=m;j++) bit.clear(j-magic[i-][j]);
}

int main(){
    freopen("a.in","r",stdin);
#ifndef debug
    freopen("a.out","w",stdout);
#endif
    while(scanf("%d%d",&n,&m), n||m){
        D(n); D(m); E;
        for(int i=;i<=n;i++)for(int j=;j<=m;j++) scanf("%d",&cost[i][j]);
        for(int i=;i<=n;i++)for(int j=;j<=m;j++) scanf("%d",&magic[i][j]);
        bit.init(mxn); for(int i=;i<=m;i++)res[i]=cost[][i];
        for(int i=;i<=n;i++){
            memset(f,,sizeof(f)); memset(g,,sizeof(g));
            dp(i,f); 
            reverse(cost[i]+,cost[i]++m); 
            reverse(magic[i]+,magic[i]++m);
            reverse(magic[i-]+,magic[i-]++m);
            reverse(res+,res++m);
            dp(i,g);
            reverse(magic[i]+,magic[i]++m);
            reverse(res+,res++m);
            for(int j=;j<=m;j++)res[j]=min(f[j],g[m-j+]);
        }
        ans=INF; for(int j=;j<=m;j++) ans=min(ans,res[j]);
        printf("%d\n",ans); 
    }
}