ICPC 国内予選2003C The Secret Number AOJ1126

イキってDPで解いたら実装重くて痛い目にあった
集中してやったのでバグは起きなかった。

dp[i][j][0] : 場所i,jをスタート地点にした時の数字の桁の最大数
dp[i][j][1～] : 最大の時の数字の列

これを i = h-1, j = w-1　（一番右下のブロック）から　i=0,j=0　までをDPする
つまり漸化式の根幹は、
i,jが数字の時 : dp[i][j][0] = max(1,dp[i+1][j][0],dp[i][j+1][0])

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


char num[] = "0123456789";
int di[] = {1,0};
int dj[] = {0,1};

bool check(int len,int a[80],int b[80]){
    for(int i = 1;i <= len;i++){
        if(a[i] == b[i]) continue;
        else if(a[i] > b[i]){
            return true;
        }else{
            return false;
        }
    }
    return false;
}

int dp[80][80][80] = {0};

int main(){
    int w,h;
    char tmp[80][80];
    int mat[80][80];
    while(1){
        cin >> w >> h;
        if(w == 0)break;
        for(int i = 0;i < h;i++) cin >> tmp[i];

        for(int i = 0;i < 80;i++){
            for(int j = 0;j < 80;j++){
                for(int k = 0;k < 80;k++){
                    dp[i][j][k] = 0;
                }
            }
        }
        
        for(int i = 0;i < h;i++){ // char から　int にする
            for(int j = 0;j < w;j++){
                mat[i][j] = -1;
                for(int k = 0;k <= 9;k++) if(num[k] == tmp[i][j]) mat[i][j] = k;
            }
        }
        
        
        int maxlen = 0,ans[80] = {0};
        for(int i = 0;i < h;i++) mat[i][w] = -1;
        for(int j = 0;j < w;j++) mat[h][j] = -1;
        
        
        for(int i = h-1;i >= 0;i--){
            for(int j = w-1;j >= 0;j--){
                if(mat[i][j] == -1) continue;
                dp[i][j][0] = 1; dp[i][j][1] = mat[i][j];
                if(mat[i][j] != 0 && maxlen <= 1){
                    maxlen = 1;
                    ans[1] = max(ans[1],mat[i][j]);
                }
                for(int k = 0;k < 2;k++){
                    int ni = i+di[k],nj = j+dj[k];
                    if(mat[ni][nj] == -1)continue;
                    if(1 + dp[ni][nj][0] > dp[i][j][0]){ // 必ず値を更新すべき場合
                        dp[i][j][0] = 1 + dp[ni][nj][0];
                        for(int ii = 0;ii < dp[ni][nj][0];ii++){
                            dp[i][j][ii+2] = dp[ni][nj][ii+1];
                        }
                        if(mat[i][j] != 0 &&  (dp[i][j][0] > maxlen || (dp[i][j][0] == maxlen && check(maxlen,dp[i][j],ans) == true))){
                            maxlen = dp[i][j][0];
                            for(int q = 1;q <= maxlen;q++) ans[q] = dp[i][j][q];
                        }
                    }else if(1 + dp[ni][nj][0] == dp[i][j][0]){ //確認が必要な場合
                        int cand[80];
                        cand[1] = mat[i][j];
                        for(int q = 0;q < dp[ni][nj][0];q++){
                            cand[q+2] = dp[ni][nj][q+1];
                        }
                        if(check(dp[i][j][0],cand,dp[i][j]) == true){
                            for(int q = 0;q < dp[ni][nj][0];q++) dp[i][j][q+2] = cand[q+2];
                        }
                        if(mat[i][j] != 0 &&  (dp[i][j][0] > maxlen || (dp[i][j][0] == maxlen && check(maxlen,dp[i][j],ans) == true))){
                            maxlen = dp[i][j][0];
                            for(int q = 1;q <= maxlen;q++) ans[q] = dp[i][j][q];
                        }
                    }
                }
            }
        }
        
        for(int i = 1;i <= maxlen;i++){
            cout << ans[i];
        }
        cout << endl;
        
    }
}