1126 The Secret Number
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1126
方針
ある位置までの可能な最大値でDPする。
ソース
#include<iostream> #include<string> using namespace std; #define REP(i,a,b) for(int i=a; i<b; ++i) #define rep(i,n) REP(i,0,n) char input[70][70]; string dp[70][70]; int comp(string s,string t) { if(s.length() != t.length()) return (s.length() - t.length()); rep(i,s.length()) if(s[i] != t[i]) return (s[i] - t[i]); return 0; } int main() { int w,h,n; while(cin>>w>>h, w|h) { string s,above,left; rep(i,h) { cin>>s; rep(j,w) { dp[i][j] = ""; input[i][j] = s[j]; } } rep(i,h) rep(j,w) { char c = input[i][j]; if(!(c <= '9' && c >= '0')) continue; above = ((i > 0 && dp[i-1][j] != "0") ? dp[i-1][j] : "") + string(1,c); left = ((j > 0 && dp[i][j-1] != "0") ? dp[i][j-1] : "") + string(1,c); dp[i][j] = (comp(above,left) <= 0) ? left : above; } string ans = ""; rep(i,h) rep(j,w) if(comp(ans,dp[i][j]) < 0) ans = dp[i][j]; cout<<ans<<endl; } }