琼斯先生按照太太提供的购物清单去超市购买物品，超市货架上的物品按顺序排列，求出买完清单上物品的最小花费。
购买的限制条件：
购买顺序必须按照清单上的顺序。如图a，必须先买完两个1，才能买2，再买20。购买时只能经过货架一次。如图b，从左到右走完，每个商品只能买或不买，不能回头买之前的。首先输入M和N两个正整数，分别代表，清单上有M个物品，超市中有N个物品。
下一行是M个正整数，代表清单上的M个物品。
然后是N行，每行为物品和它的价格
输入0 0，程序结束
一个数，购买完清单所有物品的最小价格花费，保留2位小数。
若无法全部购买，则输出Impossible
输入：
4 8 1 1 2 20 2 0.29 1 0.30 20 0.15 1 1.00 5 0.05 2 10.00 20 20.00 20 10.00输出：21.30
输入：
2 5 1 2 3 1.00 4 1.00 2 0.01 1 1.00 2 1.50输出：2.50
输入：
2 3 1 2 2 0.05 1 10.00 1 3.00输出：Impossible
此题可以用动态规划解决，首先建立一个dp数组，如下
以样例二为例
01.01.00.011.01.5m+1\n+103421201dp[1][2]2dp[2][5]此M+1行，N+1列表格（第一行为价格，方便计算）即为dp数组。
dp[1][2]表示琼斯先生在超市第2个物品时，需要购买1个物品的花费，即，在经过了3，4号物品，并且需要购买1号物品的花费。
所以，所求结果应为dp[2][5]，即经过了所有物品，并且需要购买清单上所有物品的费用。
在经过每个物品时，并且所经过物品和清单上的物品相同时，琼斯先生的动作只有买或不买，因此，dp数组的计算也是由买或不买的动作来推算。比如dp[2][5],可以是买第5个物品，或不买第5个物品的结果。如果买，那么花费就为dp[1][4]加上第5个物品的价格，如果不买，那么花费就为dp[2][4]加0。而买或不买取决于两个值的大小。
因此状态转移方程为
if（清单物品 != 经过物品），dp[i][j] = dp[i][j-1]。if（清单物品 == 经过物品），dp[i][j] = min(dp[i-1][j-1]+物品价格，dp[i][j-1])既然是计算最小花费，那么没有买完清单上的物品（比如一样不买），或是不按清单顺序购买，所得到的结果即使小，也不符合要求，因此，需要把这种特殊情况的花费设为最大值，方便后面比较大小。
初步写出的程序如下：
#include <iostream> #include <iomanip> /* cout格式化输出头文件 */ #include <algorithm> #include <cstring> #include <vector> using namespace std; class Good { /* 定义物品类，包括编号和价格*/ public: int number; double price; }; int Neednum, Goodnum; /* 清单上的数量，超市中物品数量*/ int need[101]; /* 清单上的物品*/ Good goods[100001]; /* 超市中的物品*/ double dp[101][100001]; /* DP数组*/ int main(void) { while (true) { /* 程序输入部分开始*/ cin >> Neednum >> Goodnum; if (Neednum == 0 && Goodnum == 0) break; for (int i = 0; i < Neednum; ++i) cin >> need[i]; for (int i = 0; i < Goodnum; ++i) cin >> goods[i].number >> goods[i].price; /* 程序输入部分结束*/ for (int i = 0; i <= Goodnum; i++) { dp[0][i] = 0; } for (int i = 1; i <= Neednum; i++) { dp[i][0] = INT_MAX; } for (int i = 1; i <= Neednum; i++) { for (int j = 1; j <= Goodnum; j++) { if (need[i-1] == goods[j-1].number) { dp[i][j] = min(dp[i - 1][j - 1] + goods[j - 1].price, dp[i][j - 1]); } else dp[i][j] = dp[i][j - 1]; } } /* 打印DP数组，看看设计的是否正确 for (int i = 0; i <= 1; i++) { for (int j = 0; j <= Goodnum; j++) { cout << dp[i][j] << " "; } cout << endl; } */ if (dp[Neednum][Goodnum] == INT_MAX) cout << "Impossible" << endl; else /* 保留两位小数，格式化输出*/ cout << fixed << setprecision(2) << dp[Neednum][Goodnum] << endl; } return 0; }此时用三个样例测试，输出结果均正确。但是提交会显示超出内存限制，原因可能是dp数组过大，101*100001
所以要进行状态压缩。
由于计算DP数组循环中，每一行的计算都只用到了上一行的数据，因此，可以只用两行完成计算过程，不过每一行循环完要处理一下数据。
#include <iostream> #include <iomanip> // cout格式化输出头文件 #include <algorithm> #include <cstring> #include <vector> using namespace std; class Good { // 定义物品类，包括编号和价格 public: int number; double price; }; int Neednum, Goodnum; // 清单上的数量，超市中物品数量 int need[101]; // 清单上的物品 Good goods[100001]; // 超市中的物品 double dp[2][100001]; // DP数组 int main(void) { while (true) { /* 程序输入部分开始*/ cin >> Neednum >> Goodnum; if (Neednum == 0 && Goodnum == 0) break; for (int i = 0; i < Neednum; ++i) cin >> need[i]; for (int i = 0; i < Goodnum; ++i) cin >> goods[i].number >> goods[i].price; /* 程序输入部分结束*/ for (int i = 0; i <= Goodnum; i++) { dp[0][i] = 0; // 初始化第一行，全部为0 } for (int i = 1; i <= Neednum; i++) { dp[1][0] = INT_MAX; // 每行第一个代表开始状态，没有买物品，则花费为最大值 for (int j = 1; j <= Goodnum; j++) { if (need[i-1] == goods[j-1].number) { //状态转移 dp[1][j] = min(dp[0][j - 1] + goods[j - 1].price, dp[1][j - 1]); } else dp[1][j] = dp[1][j - 1]; //状态转移 } for (int j = 0; j <= Goodnum; j++) { dp[0][j] = dp[1][j]; //第二行搬到第一行去，让下一行计算 } } // 打印dp数组调试 // for (int i = 0; i <= 1; i++) { // for (int j = 0; j <= Goodnum; j++) { // cout << dp[i][j] << " "; // } // cout << endl; // } if (dp[1][Goodnum] == INT_MAX) cout << "Impossible" << endl; else // cout格式化输出 cout << fixed << setprecision(2) << dp[1][Goodnum] << endl; } return 0; }这样就不会超出内存限制了。
