学步园

这动态规划简直就是个暴力法。另外这数据规模也太友善了

我的做法是设 dp(i,j) 为用第 i 套邮票拼凑出 j 分钱所需要的邮票数量，递推+刷表法。遇到dp值大于S或未定义的，则可以确定此套邮票最大coverage为 j-1

要留意下output格式，在题目中没说，但是在sample output中能看出来制表的痕迹。这道题惨淡的数据、大量的PE估计很多都来源于此。

Run TIme: 0.029s

#define UVa  "9-5.242.cpp"      //Stamps and Envelope Size

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

//Global Variables.
const int maxn = 10 + 5, maxcover = 1000 + 5, INF = 1<<30;
int S, N, coverage[maxn], C[maxn];      //C[i]: size of denomination i.
int denominations[maxn][maxn];
int d[maxn][maxcover];
////

int smaller(int a, int b) {
    if(C[a] != C[b]) return C[a] < C[b];
    for(int i = C[a] - 1; i >= 0; i --)
        if(denominations[a][i] != denominations[b][i])
            return denominations[a][i] < denominations[b][i];
}

int main() {
    while(scanf("%d", &S) && S) {
        scanf("%d", &N);
        for(int i = 0; i < N; i ++) {
            scanf("%d", &C[i]);
            for(int j = 0; j < C[i]; j ++)
                scanf("%d", &denominations[i][j]);
        }

        memset(d, -1, sizeof(d));

        for(int i = 0; i < N; i ++) {       //iterating all denominations
            d[i][0] = 0;
            for(int j = 0; j < maxcover; j ++) {        //iterating through all possible combinations
                int& u = d[i][j];
                if(u > S || u == -1) {
                    coverage[i] = j-1;
                    break;
                }
                for(int k = 0; k < C[i]; k ++) {        //iterating through all stamps
                    int& v = d[i][j+denominations[i][k]];
                    if(v == -1) v = u + 1;
                    else v = min(v, u+1);
                }
            }
        }
        int maxcoverage = coverage[0], ans = 0;
        for(int i = 1; i < N; i ++) {
            if(maxcoverage < coverage[i]) {
                ans = i;
                maxcoverage = coverage[i];
            }
            else if(maxcoverage == coverage[i] && smaller(i, ans))
                ans = i;
        }
        printf("max coverage =%4d :", maxcoverage);
        for(int i = 0; i < C[ans]; i ++)
            printf("%3d", denominations[ans][i]);
        printf("\n");

    }

    return 0;
}