1272.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<fstream>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const string sss="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001";
const string ss0="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
vector<string> vecs(64);
string add(string a,string b){ 
	for(int i=a.length()-1;i>=0;i--){     
	   a[i]+=(b[i]-'0');
	   if(a[i]>'9') {a[i]-=10;a[i-1]+=1;}
	}
	return a;
}
string mul(string a,int n){
	vector<int> temp(a.length());
	for(int j=0;j<a.length();j++)
		temp[j]=a[j]-'0';
	for(int i=a.length()-1;i>=0;i--){     
	    temp[i]*=n;
	}
	for(int k=a.length()-1;k>=0;k--){
		while(temp[k]>9) {temp[k]-=10;temp[k-1]+=1;}	
	}
	for(int l=0;l<a.length();l++){
        a[l]=char(temp[l]+'0');
	}
	return a;
}
void output(string s){
    int l,m,i,f=-1;
	for(i=0;i<s.length();i++){
		if(s[i]!='0') {f=i;break;}
	}
    l=s.length()-f;
	m=l%3;
	if(m==0){
		l=0;
        for(i=f;i<s.length();i++){
            cout<<s[i];
			l++;
			if(l==3&&i!=s.length()-1) {cout<<",";l=0;}
		}
	}
	else if(m==1){
		l=2;
        for(i=f;i<s.length();i++){
            cout<<s[i];
			l++;
			if(l==3&&i!=s.length()-1) {cout<<",";l=0;}
		}
	}
	else{
		l=1;
        for(i=f;i<s.length();i++){
            cout<<s[i];
			l++;
			if(l==3&&i!=s.length()-1) {cout<<",";l=0;}
		}
	}
	cout<<endl;
}
void fillchar(string & s){
    while(s.length()<22) s.insert(s.end(),' ');
}
void fillzone(string & s){
    while(s.length()<101) s.insert(s.begin(),'0');
}
void sub(string & o,string & temps){
     int i;
	 //cout<<o<<endl<<temps<<endl;
	 for(i=0;i<101;i++){
        o[i]-=(temps[i]-'0');
	 }
	 for(i=100;i>=1;i--){
		 if(o[i]<'0'){o[i]+=10;o[i-1]-=1;}
	 }
}
int cansub(string & o,string s){
	int i,j,k,f=0;
	string temps;
	
	for(i=26;i>=1;i--){
       temps=mul(s,i);
	   
	   if(o>temps){
           f=i;break;
	   }
	}
	if(f){
	sub(o,temps);
	}
	return f;
}
int main(){
vecs[0]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001";
vecs[1]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000026";
vecs[2]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000676";
vecs[3]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000017576";
vecs[4]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000456976";
vecs[5]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011881376";
vecs[6]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000308915776";
vecs[7]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008031810176";
vecs[8]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000208827064576";
vecs[9]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000005429503678976";
vecs[10]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000000141167095653376";
vecs[11]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000003670344486987776";
vecs[12]="00000000000000000000000000000000000000000000000000000000000000000000000000000000000095428956661682176";
vecs[13]="00000000000000000000000000000000000000000000000000000000000000000000000000000000002481152873203736576";
vecs[14]="00000000000000000000000000000000000000000000000000000000000000000000000000000000064509974703297150976";
vecs[15]="00000000000000000000000000000000000000000000000000000000000000000000000000000001677259342285725925376";
vecs[16]="00000000000000000000000000000000000000000000000000000000000000000000000000000043608742899428874059776";
vecs[17]="00000000000000000000000000000000000000000000000000000000000000000000000000001133827315385150725554176";
vecs[18]="00000000000000000000000000000000000000000000000000000000000000000000000000029479510200013918864408576";
vecs[19]="00000000000000000000000000000000000000000000000000000000000000000000000000766467265200361890474622976";
vecs[20]="00000000000000000000000000000000000000000000000000000000000000000000000019928148895209409152340197376";
vecs[21]="00000000000000000000000000000000000000000000000000000000000000000000000518131871275444637960845131776";
vecs[22]="00000000000000000000000000000000000000000000000000000000000000000000013471428653161560586981973426176";
vecs[23]="00000000000000000000000000000000000000000000000000000000000000000000350257144982200575261531309080576";
//ifstream cin("in.txt");
string s;
int i,j,k;
while(cin>>s&&s!="*"){
	if(s[0]<='z'&&s[0]>='a'){
		string temp=ss0;
		for(i=s.length()-1;i>=0;i--){
            temp=add(temp,mul(vecs[s.length()-1-i],(s[i]-'a'+1)));
		}
		fillchar(s);
		cout<<s;
		output(temp);
	}
	else{
        k=0;
		string res,copy=s;
		fillzone(s);
		for(i=23;i>=0;i--){
           j=cansub(s,vecs[i]);
		   if(j||k){
               res.insert(res.end(),char('a'+j-1));
			   k=1;
		   }
		}
		res[res.length()-1]+=1;
		fillchar(res);
		cout<<res;
		output(copy);
	}
}
}