ZOJ 1524 Supermarket

動態規劃

F[i][j]：列表上第i個物品和supermarket裡面第ｊ個商品。此時可以花的最小費用。

a[i] == b[j]    F[i][j] = min(F[i][j-1], F[i-1][j-1] + p[j])

a[i] != b[j]     F[i][j] = F[i][j-1]

初始化為最大值inf

[cpp]
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std; 
#define N 100002  
#define M 102  
#define inf 1e10  
int a[M], b[N], n, m; 
double p[N], f[2][N]; 
int main() { 
    while (scanf("%d%d", &m, &n) == 2 && n+m) { 
        for (int i=1; i<=m; i++) scanf("%d", &a[i]); 
        int cur = 1; 
        f[cur][0] = inf; 
        for (int i=1; i<=n; i++) { 
            scanf("%d%lf", &b[i], &p[i]); 
            if (b[i] == a[1]) f[cur][i] = min(f[cur][i-1], p[i]); 
            else f[cur][i] = f[cur][i-1]; 
        } 
        for (int i=2; i<=m; i++) { 
            cur = 1 - cur; 
            for (int j=0; j<=n; j++) f[cur][j] = inf; 
            for (int j=1; j<=n; j++) { 
                if (a[i] == b[j]) f[cur][j] = min(f[cur][j-1], f[1-cur][j-1]+p[j]); 
                else f[cur][j] = f[cur][j-1]; 
            } 
        } 
        if (f[cur][n] < inf) printf("%.2lf\n", f[cur][n]); 
        else printf("Impossible\n"); 
    } 
    return 0; 
}