题解 GDFZOJ 【649】 邮票问题

· · 个人记录

看原题戳这儿

一、审题

给定一个信封，最多只允许粘贴n(n\le100)张邮票，我们现在有m(m\le100)种邮票，面值分别为：x_1,x_2,······,x_m(xi\le255,\text{为正整数})分，并假设各种邮票都有足够多张。要求计算所能获得的邮资最大范围。即求最大值MAX，使在1-MAX之间的每一个邮资值都能得到。

很明显，这是一道Dp的题目

二、做题

众所周知，Dp的题目主要就是要推式子，所以就开始推式子吧

我们先定义一个状态f_j表示要凑到面值为j分的邮票最少需要多少张邮票，容易得到，若果我们有一张面值为x的邮票，那么f_j=f_{j-x}+1，不过有可能这并不是最优的解法呀，所以我们需要取一个max，于是我们的式子就这么简单地推出来了:

f_j=max(f_j,f_{j-x}+1)

三、代码

#include<bits/stdc++.h>
using namespace std;
int a,b,i,j,ans;
int f[2000000];
int main() 
{
    scanf("%d%d",&a,&b);
    for(i=1;i<=2000000;i++) f[i]=1e9;
    f[0]=0;
    for (i=1;i<=b;i++)
    {
        int x;
        scanf("%d",&x);
        for(j=x;j<=2000000;j++)
        if(f[j-x]+1<=a) f[j]=min(f[j],f[j-x]+1);
    } 
    ans=0;
    for(i=1;i<=2000000;i++)
    if(f[i]==1e9)
    {
        ans=i-1;
        break;
    }
    printf("MAX=%d\n",ans);
    return 0;
}