首页 > 代码库 > 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