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; }
木有理解..
哪天上课给你说说?
Soga!贼暴力~ 😆