AOJ 1126 : The Secret Number
問題リンク:The Secret Number | Aizu Online Judge
問題概要:
略
使用した言語:C++
解法;
左と上をみて値の大きいほうを保存していく
ただし普通に比較するのではなく、リーディング0も考慮しなければならない
cmp2は作ったけどいらなかったっぽい
コード:
#include<iostream> #include<algorithm> #include<cstdio> #include<sstream> #include<cstring> #include<vector> using namespace std; bool cmp1(const string& a,const string& b) { int size_a,size_b; int start_a,start_b; start_a = start_b = 0; size_a = a.size(),size_b = b.size(); if(a[0] == '0') for(int i=0;i<a.size() && a[i] == '0';i++) size_a--,start_a++; if(b[0] == '0') for(int i=0;i<b.size() && b[i] == '0';i++) size_b--,start_b++; if(size_a != size_b) return size_a < size_b; for(int i=0;i<size_a;i++) { if(a[start_a+i] != b[start_b+i]) return a[start_a+i] < b[start_b+i]; } return true; } bool cmp2(const string& a,const string& b) { if(a.size() != b.size()) return a.size() < b.size(); for(int i=0;i<a.size();i++) { if(a[i] != b[i]) return a[i] < b[i]; } return true; } int main() { int W,H; while(cin >> W >> H,W|H) { vector<vector<string> > G; G.resize(H); for(int i=0;i<H;i++) { G[i].resize(W); string line; cin >> line; for(int j=0;j<W;j++) { G[i][j] = line[j]; } } string G2[H][W]; string ans = ""; for(int i=0;i<H;i++) { for(int j=0;j<W;j++) { if(isalpha(G[i][j][0])) continue; G2[i][j] = max(G2[i][j],G[i][j],cmp1); string A,B; A = B = G2[i][j]; if(j-1 >= 0 && !isalpha(G[i][j-1][0])) A = max(G2[i][j],G2[i][j-1]+G2[i][j],cmp1); if(i-1 >= 0 && !isalpha(G[i-1][j][0])) B = max(G2[i][j],G2[i-1][j]+G2[i][j],cmp1); G2[i][j] = max(A,B,cmp1); ans = max(G2[i][j],ans,cmp1); } } for(int i=0;i<ans.size()&&ans[i] == '0';i++) ans[i] = ' '; stringstream ss; ss << ans; ss >> ans; cout << ans << endl; } return 0; }