当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 【题解】洛谷 P2725 邮票 Stamps

【题解】洛谷 P2725 邮票 Stamps

2019年09月22日  | 移动技术网IT编程  | 我要评论

目录

题目

p2725 邮票 stamps

思路

$\texttt{dp}$。$\texttt{dp[i]}$表示拼出邮资$i$最少需要几张邮票。
状态转移方程：$\texttt{dp[i]=min(dp[i],dp[i-value]+1)}$

$code$

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[51],f[2000001];
inline void read(int &t){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    t=f?-x:x;
}

int main(){
    read(n),read(m);
    int maxx=0;
    memset(f,0x3f3f3f,sizeof(f));
    for(int i=1;i<=m;++i){
        read(a[i]);
        maxx=max(a[i],maxx);
    }
    int stop=maxx*n;
    f[0]=0;
    for(int j=1;j<=m;++j){
        for(int i=1;i<=stop;++i){
            if(a[j]>i) continue;
            f[i]=min(f[i],f[i-a[j]]+1);
        }
    }
    for(int i=1;i<=stop;++i){
        if(f[i]>n){
            printf("%d\n",i-1);
            return 0;
        }
    }
    printf("%d\n",stop);
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网