2030 The Secret Number

「2030 The Secret Number」の編集履歴（バックアップ）一覧はこちら

「2030 The Secret Number」(2006/04/17 (月) 01:57:41) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2030 The Secret Number
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2030
**解答方針
典型的な動的計画法で解ける．

二次元配列valtable（valtable[i][j]はi行j列を末尾とする数字の最大値）を左上から埋めていく．その際の基本式は
 //table[i][j] 入力のi行j列の文字
 //valtable[i][j] i行j列を末尾とする数字の最大値
 
 if(table[i][j]が数字) then
   valtable[i][j] = max(valtable[i][j-1],valtable[i-1][j])*10 + table[i][j]の値;
 else
   valtable[i][j] = 0;
である．i=0やj=0の場合は例外的に処理する必要があることに注意する．

なお，掛け算，足し算をBigIntegerで行っているのは勿論実行効率が悪く，文字列処理によって実現すべきだが，今回は楽をすることを優先させてみた．
**解答例
 import java.util.*;
 import java.math.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int w = sc.nextInt();
             int h = sc.nextInt();
             if(w==0&&h==0) break;
             char[][] table = new char[h][w];
             for(int i=0;i<h;i++){
                 String line = sc.next();
                 table[i] = line.toCharArray();
             }
             Solver sol = new Solver(w,h,table);
             System.out.println(sol.solve());
         }
     }
 }
 
 class Solver{
     int w;
     int h;
     char[][] table;
     BigInteger[][] valtable;
     Solver(int sw,int sh,char[][] stable){
         w = sw;
         h = sh;
         table = stable;
         valtable = new BigInteger[h][w];
     }
     public BigInteger solve(){
         for(int i=0;i<Math.min(h,w);i++){
             compute(i,i);
             for(int j=i+1;j<w;j++) compute(i,j);
             for(int j=i+1;j<h;j++) compute(j,i);
         }
         
         BigInteger ret = BigInteger.ZERO;
         for(int i=0;i<h;i++){
             for(int j=0;j<w;j++){
                 ret = ret.max(valtable[i][j]);
             }
         }
         return ret;
     }
     public void compute(int i,int j){
         if(!isDisit(table[i][j])) valtable[i][j] = BigInteger.ZERO;
         else{
             if(i>0&&j>0){
                 valtable[i][j] = (valtable[i-1][j].max(valtable[i][j-1]))
                     .multiply(BigInteger.TEN).add(new BigInteger(Character.toString(table[i][j])));
             }
             else if(i>0){
                 valtable[i][j] = valtable[i-1][j]
                     .multiply(BigInteger.TEN).add(new BigInteger(Character.toString(table[i][j])));
             }
             else if(j>0){
                 valtable[i][j] = valtable[i][j-1]
                     .multiply(BigInteger.TEN).add(new BigInteger(Character.toString(table[i][j])));
             }
             else{
                 valtable[i][j] = new BigInteger(Character.toString(table[i][j]));
             }
         }
     }
     public static boolean isDisit(char c){
         if('0'<=c&&c<='9') return true;
         else return false;
     }
 }