Posted on 2011-11-06 22:04
C小加 閱讀(1484)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
題意：在一個正方形的國度里住著正方形的人.在這個國家里,所有的東西都是正方形的.該國的國會通過了一項關于土地的法律,依照法律,該國的國民有買土地的權利,當然,土地的買賣也是按照正方形進行.而且,買賣的土地的邊長必須是整米數,每買一塊土地,必須付款(用當地的錢幣),每買一塊地,買主會得到一份土地所有者的證明.
一個市民打算把他的錢投資到土地上,因為都只能買邊長為整數的正方形地,他希望土地的塊數最小.他認為:"這使我在交稅時,更方便",他終于購地成功. 你的任務是找出他購地的塊數,以便發給他地主證書.
輸入包含一個自然數N,N<=60000,表示他能買多少方土地
輸出他得到的土地塊數.
思路：之前在Ural上邊做過，當時做的時候挺困難的，今天在NYOJ上看到有人剛出了這道題，就果斷的拿下了FB（除了上傳者AC的）。
完全背包，動態轉移方程式為f(i)=min(f(i),f(i-j*j)+1);我想出了兩種結構，時間都差不多。
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=60000;
int f[MAXN];
int main()
{
for(int i=0;i<=MAXN;i++) f[i]=i;//方法一
for(int i=2;i*i<=MAXN;i++)
{
for(int j=i*i;j<=MAXN;j++)
{
f[j]=min(f[j],f[j-i*i]+1);
}
}
/* for(int i=4;i<=MAXN;i++)//方法二
{
for(int j=2;j*j<=i;j++)
{
f[i]=min(f[i],f[i-j*j]+1);
}
}
*/
int n;
while(scanf("%d",&n)&&n)
{
printf("%d\n",f[n]);
}
return 0;
}