TopCoder SRM 354 Div1 Easy DateFormat

問題

米国式では日付は月/日と書き、英国式では日付は日/月と書く。
日付のリストが与えられるが、書式がどちらで書かれているか解らない。

日付は、早い順に並んでいるものとするとき、日付を全て米国式で記し、つなげた文字列を返せ。
候補が複数ある場合は辞書順で最小のものを返せ。

制約条件

日付の数≦1000くらい？

方針

dp[pos][i]を、リストのpos番目まで見たとき、現在の日数i日目とすることができるかを持つようなDP+経路復元をした。

よく考えたら、日付を早いほうとして貪欲に使うだけでよかった。

ソースコード

vs date,ans;
int n,dp[800][367];

int day[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int sum[14];
int get(string a){
	int m=atoi(a.substr(0,2).c_str());
	int d=atoi(a.substr(3).c_str());
	if(1<=m&&m<=12&&d<=day[m])return sum[m]+d;
	return -1;
}
string rev(string a){
	a=a.substr(3)+"/"+a.substr(0,2);
	return a;
}

int rec(int pos,int d){
	if(pos>=n)return 1;
	if(dp[pos][d]>=0)return dp[pos][d];
	int a=get(date[pos]), b=get(rev(date[pos]));
	vi v;
	if(a>=0&&a>d)v.pb(a);
	if(b>=0&&b>d)v.pb(b);
	sort(all(v));
	
	dp[pos][d]=0;
	rep(i,v.size()){
		if(rec(pos+1,v[i]))return dp[pos][d]=v[i];
	}
	return 0;
}
void make(){
	ans.clear();
	int d=0;
	rep(i,n){
		int nd=dp[i][d];
		for(int m=12;;m--)if(sum[m]<nd){
			char buf[9];
			sprintf(buf,"%02d/%02d",m,nd-sum[m]);
			ans.pb(buf);
			break;
		}
		d=nd;
	}
}

class DateFormat {
	public:
	string fromEuropeanToUs(vector <string> dateList) 
	{
		rep(i,13)sum[i+1]=sum[i]+day[i];
		
		date.clear();
		stringstream ss(accumulate(all(dateList),string()));
		string s;
		while(ss>>s)date.pb(s);
		
		n=date.size();
		memset(dp,-1,sizeof(dp));
		if(!rec(0,0))return "";;
		make();
		string res="";
		rep(i,ans.size())res+=ans[i]+" ";
		res.erase(res.end()-1);
		return res;
	}
};