poj1742 동적 기획 클래식 다중 가방

1628 단어 동적 기획
n가지의 서로 다른 액면가가 있는 동전은 액면가가 각각 A1, A2, A3이다.AN, 수량은 각각 C1, C2, C3,,,, CN입니다.주어진 숫자 m에 이 동전들이 m보다 작은 숫자 중 어떤 숫자를 구성할 수 있는지 물어보고 이 숫자를 출력한다.
처음에는 1부터 m까지 이 동전들로 구성될 수 있는지 판단하려고 했지만 동전의 수량을 판단할 때 문제가 생겨서 동전마다 사용하는 수량을 집계하기 어려웠고,
나중에 인터넷에 검색해 보니 동전 종류별로 시작해서 동전 종류별로 구성할 수 있는 수를 기록해 놓으면 동전 종류별로 숫자를 집계할 때 통계가 잘 된다.다른 사람의 생각을 거울로 삼았다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))

using namespace std;

typedef long long ll;
typedef pair pii;

inline int in()
{
    int res=0;char c;
    while((c=getchar())'9');
    while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
    return res;
}

int value[110];
int num[110];
int cnt[100010];
bool dp[100010];

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m) && n)
    {
        mem(dp,0);
        for(int i=1;i<=n;i++)
        {
            value[i]=in();
        }
        for(int i=1;i<=n;i++)
        {
            num[i]=in();
        }
        int ans=0;
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            mem(cnt,0);//       cnt    
            for(int j=value[i];j<=m;j++) //               
            {
                if(!dp[j] && dp[j-value[i]] && cnt[j-value[i]]
Dockerfile 미 러 크기 줄 이 는 방법
Python 3 + Django + uwsgi + nginx 배치

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage