首页 > 代码库 > 小P的故事——神奇的换零钱&&人活着系列之平方数

小P的故事——神奇的换零钱&&人活着系列之平方数

2024-07-15 20:56:03   219人阅读

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2777&cid=1219

这题不会，看了别人的代码

#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>using namespace std;int dp[32770];int main(){    int n,i,j;    int w[4]= {0,1,2,3};    memset(dp,0,sizeof(dp));    dp[0]=1;    for(i=1; i<=3; i++)    {        for(j=w[i]; j<=32768; j++)        {            dp[j]=dp[j]+dp[j-w[i]];        }    }    while(scanf("%d",&n)!=EOF)    {        printf("%d\n",dp[n]);    }    return 0;}

 http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2934

这题就是换零钱的变形

#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>using namespace std;int main(){    int T,n,dp[501];    int w[21]= {0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400};    memset(dp,0,sizeof(dp));    dp[0]=1;    for(int i=1; i<=20; i++)    {        for(int j=w[i]; j<=500; j++)        {            dp[j]=dp[j]+dp[j-w[i]];        }    }    while(scanf("%d",&n)!=EOF)    {        printf("%d\n",dp[n]);    }    return 0;}

 


联系
我们