The Secret Number
2006.07.04 23:48 ACM/ICPC
[問題] ACM/ICPC Japan Domestic 2003: Problem C
[解説]
Dynamic Programming
上から下、左から右、の順に各セルにおける最適な文字列を計算していけば、現在のセルの値を計算する時に、左のセルと上のセルがすでに最適解となっているので、それらの値の大きい方を選び、現在のセルに対応する文字をくっつけていきます。
[プログラム例]
[解説]
Dynamic Programming
上から下、左から右、の順に各セルにおける最適な文字列を計算していけば、現在のセルの値を計算する時に、左のセルと上のセルがすでに最適解となっているので、それらの値の大きい方を選び、現在のセルに対応する文字をくっつけていきます。
[プログラム例]
// @author yutaka C++ #include<string> #include<iostream> #define MAX 72 using namespace std; int row, column; char M[MAX][MAX]; string T[MAX][MAX], secret; string max( string str1, string str2 ){ if ( str1.size() == str2.size() ){ return ( str1 > str2 ) ? str1 : str2; } else { return ( str1.size() > str2.size() ) ? str1 : str2; } } void compute(){ secret = ""; for ( int i = 1; i <= row; i++ ){ for ( int j = 1; j <= column; j++ ){ if ( isalpha( M[i][j] ) ) continue; T[i][j] = max( T[i-1][j], T[i][j-1] ) + M[i][j]; // 最初の 0 を��辰9 if ( T[i][j][0] == '0' ) T[i][j] = T[i][j].substr(1, T[i][j].size()-1); secret = max( secret, T[i][j] ); } } cout << secret << endl; } bool input(){ cin >> column >> row; if ( column == 0 && row == 0 ) return false; // 番弗踉; for ( int j = 0; j <= column; j++ ) { M[0][j] = 'A'; T[0][j] = "";} for ( int i = 0; i <= row; i++ ) { M[i][0] = 'A'; T[i][0] = "";} for ( int i = 1; i <= row; i++ ){ for ( int j = 1; j <= column; j++ ){ cin >> M[i][j]; T[i][j] = ""; } } return true; } main(){ while ( input() ) compute(); }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |