URAL 1073. Square Country（完全背包）

今天發生了各種事情，全是壞事，悲劇。狀態降到了低谷。原本一道簡單的題想跑偏了。

有簡化一下，拿n元錢去買地，已知每塊地都是正方形，而且它的花費是a*a(a邊長)。問這些錢所買地的最少塊數，錢要正好花完。

思路：完全背包問題。每種地都是無限的。每塊地的花費是a*a,權值是1。所以問題就轉化為裝滿容器n所得到的最小權值。

所以dp[i] = min ( dp[i], dp[ i-cost[j] ]+1 ) 。

#include 
#include 
#include 
#include 
using namespace std;

int dp[60010];
int cost[245];

int main()
{
	for(int i = 1; i <= 245; i++)
		cost[i] = i*i;
	int v;
	while(~scanf(%d,&v))
	{
		dp[0] = 0;
		for(int i = 1; i <= v; i++)
			dp[i] = i;

		for(int i = 1; i <= sqrt(v); i++)
		{
			for(int j = i*i; j <= v; j++)
				dp[j] = min( dp[j], dp[j-i*i]+1);
		}
		printf(%d
,dp[v]);
	}
	return 0;
}