ZOJ 1524 Supermarket (DP)

于 2011年03月15日 发布在 算法&&ACM 跳到评论

ZOJ 1524 Supermarket

Mr. Jones得到一份购物清单,清单上按顺序写出了需要购买的物品,在买东西的时候要按照顺序弄。。。。另外,题目还给出了,超市中的物品排列情况,买东西的时候还要按照物品的顺序进行购买,显然,可能会有各种不同的购买方案,同时花费也是变化着的,要求输出最少的花费。

设一个V[i]表示,购买前i+1件物品所需要的最少费用,L[i]表示列表上商品的类型 ,K[i]表示超市里的商品类型,P[i]商品价格price。由于要随着商品的排列情况进行选择,从第一件商品开始进行选择,层循环因为用到滚动数组,所以要从M-1开始循环。。。。每找到一个便宜的价格就更新,最终V[M-1]就是结果。。。。      如果这样不好理解的话,可以这样V[i][j]表示用超市中前i个物品,买清单上前个j物品所需花费的最少量。。。 好好想想。。好好想想。。。


#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<sstream>
#include<algorithm>
#include<iomanip>
using namespace std;
int M,N;
int L[ 100 ],K[ 100000 ];
double V[ 100 ],P[ 100000 ];
int main(void)
{
    int i,j;

    while( cin >> M >> N && N ){
        for( i = 0; i < M; i++ )
            cin >> L[i], V[i] = 1e100;
        for( i = 0; i < N; i++ )
            cin >> K[i] >> P[i];

        for( i = 0; i < N; i++ ){//核心代码
            for( j = M-1; j >= 1; j-- )
                if( L[j] == K[i] && V[j] > V[j-1] + P[i] )
                    V[j] = V[j-1] + P[i];
            if( L[j] == K[i] && V[j] > P[i] )
                V[j] = P[i];
        }
        if( V[M-1] == 1e100 )
            cout << "Impossible\n";
        else
            cout << setiosflags(ios::fixed)
                 << setprecision(2)
                 << V[M-1] << endl;
    }
    return 0;
}

本文共有 3条评论 | 沙发:文章评论

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)