2130-Billion Million Thousand

新幹線から

問題概要

数詞とw_iその大きさp_iが与えられる．
数字は数詞をいくつか繋げた文字列(以下数詞文字列)によって表わされ，その数詞の大きさの合計で表わせる．
例えば(thousand,3),(milion,6)が与えられた場合を考える．
9を表わすにはmillonthousandとthousandmilionの2通りの表わし方がある．
18を表わすにはmilionmilionmilionやthousandmilionmilionthousandなどの表わし方がある．

また(y,3),(yy,9)が与えられた場合を考える．
するとyyyはy-y-y(9)やyy-y(12)やy-yy(12)のように複数の解釈が出来る．

さて，与えられた数詞文字列によって表わされた数を表わすことが出来る最小の数詞文字列の長さを求めよ．
ただし与えられた数詞文字列によって表わされた数の解釈が複数ある場合最も大きいものが選択される．

解法

ある数字を表わす最小の文字列を動的計画法で求め，さらに与えられた数詞文字列が表わす最大の数を動的計画法で求める．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
typedef pair<string,int> P;
vector<P> data;
string input;
int length;
const int MAX=100001;
int TCASE=0;
int main(){
	for(int n;cin>>n,n;){
		data=vector<P>(n);
		REP(i,n){
			cin>>data[i].first>>data[i].second;
		}
		cin>>input;
		vector<int> made(MAX,999999);
		made[0]=0;
		REP(i,MAX){
			REP(j,n){
				int l=data[j].first.size();
				if(i+data[j].second>=MAX)continue;
				made[i+data[j].second]=min(made[i+data[j].second],made[i]+l);
			}
		}
		length=input.size();
		set<int> m[length+1];
		m[0].insert(0);
		REP(i,length){
			REP(j,n){
				int l=data[j].first.size();
				if(i+l>length)continue;
				if(input.substr(i,l)!=data[j].first)continue;
				FOR(it,m[i])
					m[i+l].insert(*it+data[j].second);
			}
		}
		int ans=999999;
		ans=min(ans,made[*m[length].rbegin()]);

		cout<<"Case "<<++TCASE<<": "<<ans<<endl;
	}
}