首页 > 代码库 > POJ 2030
POJ 2030
简单DP题。
可以用运算符重载来写,简单一些。
#include <iostream>#include <cstdio>#include <cstring>#include <string.h>using namespace std;class STRS{public: char str[100]; void operator=(STRS b){ strcpy(str,b.str); } STRS operator+(char b){ STRS tmp; strcpy(tmp.str,str); int leng=strlen(tmp.str); if(tmp.str[0]==‘0‘){ tmp.str[0]=b; tmp.str[1]=‘\0‘; } else{ tmp.str[leng]=b; tmp.str[leng+1]=‘\0‘; } return tmp; } bool operator >(STRS b){ int al=strlen(str); int bl=strlen(b.str); if(al>bl) return true; else if(bl>al) return false; for(int i=0;i<al;i++){ if(str[i]>b.str[i]) return true; else if(str[i]<b.str[i]) return false; } return false; } void initial(){ strcpy(str,"0"); }};STRS gp[100],dp[100][100],answer;int n,m;int main(){ STRS tmpt; while(scanf("%d%d",&m,&n)!=EOF){ if(n==0&m==0) break; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j].initial(); answer.initial(); for(int i=1;i<=n;i++) scanf("%s",gp[i].str+1); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(gp[i].str[j]>=‘0‘&&gp[i].str[j]<=‘9‘){ dp[i][j]=dp[i][j]+gp[i].str[j]; tmpt=dp[i][j-1]+gp[i].str[j]; if(tmpt>dp[i][j]) dp[i][j]=tmpt; tmpt=dp[i-1][j]+gp[i].str[j]; if(tmpt>dp[i][j]) dp[i][j]=tmpt; if(dp[i][j]>answer) answer=dp[i][j]; } } } printf("%s\n",answer.str); } return 0;}
POJ 2030
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。