61
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;
}
最後更新：2017-04-04 07:03:16