hdu 2069 Coin Change(dp 모)

2066 단어 change

 
dp
#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<iostream>

using namespace std;

int op[10]={1,5,10,25,50};

int dp[300][300];

void fun()

{

    int i,j,k;

    memset(dp,0,sizeof(dp));

    dp[0][0]=1;

    for(j=0;j<5;j++)

    {

        for(i=1;i<=100;i++)

        {

            for(k=op[j];k<=250;k++)

            {

                dp[i][k]+=dp[i-1][k-op[j]];

            }

        }

    }

}

int main()

{

    int n;

    int i,j,k;

    fun();

    /*for(i=0;i<=20;i++)

    {

        printf("%d %d
",i,dp[2][i]); }*/ while(scanf("%d",&n)!=EOF) { int ret=0; for(i=0;i<=100;i++) { ret+=dp[i][n]; } printf("%d
",ret); } return 0; }

 
 
모함수
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int c1[300][200],c2[300][200];

int op[10]={1,5,10,25,50};



void fun()

{

    int i,j,k,l;

    memset(c2,0,sizeof(c2));

    memset(c1,0,sizeof(c1));

    c1[0][0]=1;

    for(i=0;i<5;i++)

    {

        //cout<<i<<endl;

        for(j=0;j<=250;j++)

        {

            for(k=0;j+k*op[i]<=250;k++)

            {

               for(l=0;l+k<=100;l++)

               {

                   c2[j+k*op[i]][l+k]+=c1[j][l];

               }

            }

        }

        //cout<<i<<endl;

        for(j=0;j<=250;j++)

        {

            for(l=0;l<=100;l++)

            {

                c1[j][l]=c2[j][l];

                c2[j][l]=0;

            }

        }

    }

}

int main()

{

    int n;

    int i,j,k;

    fun();

    while(scanf("%d",&n)!=EOF)

    {

        int ans=0;

        for(i=0;i<=100;i++)

        {

            ans+=c1[n][i];

        }

        printf("%d
",ans); } return 0; }

좋은 웹페이지 즐겨찾기