ZOJ 1524 Supermarket (DP)

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;
}