HDU1398 DP

简介:

这题用母函数或者DP都可以 我用DP做的 感觉还是DP还是熟练一些 开一个标记数组 一个答案数组 如果标记数组

的值为真 那么就证明有一种硬币排列出j的值 那么从j再往上加i*i 的同时更新ans dp 就行了 用脑子模拟一下就可以了

 

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool dp[310];
int ans[310];
int main()
{
    int n;
    memset(dp,0,sizeof(dp));
    memset(ans,0,sizeof(ans));
    dp[0]=1;
    ans[0]=1;
    for(int i=1; i<=17; i++)
        for(int j=0; j+i*i<305; j++)
            if(dp[j])
            {
                dp[j+i*i]=1;
                ans[j+i*i]+=ans[j];
            }
    while(~scanf("%d",&n)&&n)
        printf("%d\n",ans[n]);
    return 0;
}

目录
相关文章
|
6月前
[leetcode ~dp ]279. 完全平方数
[leetcode ~dp ]279. 完全平方数
|
存储 算法
dp 就 dp ,数位dp是什么意思 ?
dp 就 dp ,数位dp是什么意思 ?
364 0
codeforces118——D. Caesar‘s Legions(DP)
codeforces118——D. Caesar‘s Legions(DP)
83 0
codeforces118——D. Caesar‘s Legions(DP)
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)