【动态规划】超级市场

动态规划DP

传送门：CodeVS1253

由于按顺序买菜，因此用$f_x$记录买前x道菜所需的钱，然后转移 要买第x道菜必须前x道菜都买好了 可以枚举买第i道菜作为菜单上的第j道菜，那么菜的品种必须一样 转移如下

$f_i=min(f_i,f_i-1+cost_j)$

转移问题不大，但枚举的时候j要倒序枚举，否则同一道菜可能会被计算多次（参考完全背包和01背包的区别）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
int n,m,i,a[130],b[100030];
double c[100030],f[100030];
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=m;i++) scanf("%d%lf",&b[i],&c[i]);
	
	for (int i=1;i<=n;i++) f[i]=1<<30;
	
	for (int i=1;i<=m;i++)
		for (int j=n;j>=1;j--)
			if (a[j]==b[i])
				if (f[j]>=f[j-1]+c[i])
					f[j]=f[j-1]+c[i];
	
	if (f[n]==1<<30) printf("Impossible\n");
	else printf("%.2f\n",f[n]);
	
	return 0;
}