POJ 1297 Supermarket

問題

n個の買い物すべき商品のリストが与えられる。
商品はリストに登場する順に、全てを買わなければならない。

m個の棚の情報が与えられる。
棚には一つの商品が置かれていて、値段が決まっている。
棚は、与えられた順に見るものとし、戻ることはできない。（棚の商品を買わないことはできる）

与えられたリストの商品を一番安く買うために必要なお金はいくらか、求めよ。
与えられたリストの商品を全て買うことが不可能な場合、Impossibleを出力せよ。

制約条件

リストの商品の数≦100
棚の数≦100000

方針

まず、商品の番号が整数で指定されるのが面倒なので、座標圧縮する。
商品番号iが、リストのどこに出現するかを、二次元ベクタとして持っておく。
（1番の商品はリストの3番目と5番目に出現する、2番の商品は……という風に）

ベクタが出来たら、
dp[i]をリストのi番目までの商品を買うのにかかる最小の金額として、
ベクタを使ってdpテーブルを更新していくようなdpができる。

DPの部分でかかる計算時間はO(m)時間で、
座標圧縮にかかる計算時間はO( (n+m)log (n+m) )時間となり、制限時間に間に合う。

ソースコード

int n,m,buy[100],goods[100000];
double price[100000];

int nums[100100],sz;
double dp[101];

int main()
{
	while(scanf("%d%d",&m,&n),m){
		rep(i,m)scanf("%d",buy+i), nums[i]=buy[i];
		rep(i,n)scanf("%d%lf",goods+i,price+i), nums[i+m]=goods[i];
		
		sort(nums,nums+n+m); sz=unique(nums,nums+n+m)-nums;
		map<int,int> M;
		rep(i,sz)M[nums[i]]=i;
		
		vector<vi> pos(sz);
		rep(i,m)pos[M[buy[i]]].pb(i);
		
		rep(i,m+1)dp[i]=INF;
		dp[0]=0;
		
		rep(i,n){
			int g=M[goods[i]];
			for(int j=(int)pos[g].size()-1;j>=0;j--)
				dp[pos[g][j]+1]=min(dp[pos[g][j]+1],dp[pos[g][j]]+price[i]);
		}
		if(dp[m]==INF)puts("Impossible");
		else printf("%.2f\n",dp[m]);
	}
	return 0;
}