很简单的dp，贪心会WA
1 #include <iostream>
2 using namespace std;
3 const int OO=1000000;
4 int n;
5 int num[261];
6 int dp[60001];
7 int main(){
8 scanf("%d",&n);
9 for (int i=1;i<=260;++i) num[i]=i*i;
10 int ans=0;
11 int p=260;
12 while (num[p]>n) --p;
13 for (int i=1;i<=n;++i) dp[i]=OO;
14 for (int i=0;i<=n;++i)
15 for (int j=1;j<=p;++j) if (i+num[j]<=n&&dp[i]+1<dp[i+num[j]]) dp[i+num[j]]=dp[i]+1;
16 cout<<dp[n];
17 }
posted on 2008-11-08 17:54
Joseph 阅读(163)
评论(0) 编辑 收藏 引用