URAL 1073. Square Country（完全双肩包）

URAL 1073. Square Country（完全背包）

http://acm.timus.ru/problem.aspx?space=1&num=1073

今天发生了各种事情，全是坏事，悲剧。状态降到了低谷。原本一道简单的题想跑偏了。

有简化一下，拿n元钱去买地，已知每块地都是正方形，而且它的花费是a*a(a边长)。问这些钱所买地的最少块数，钱要正好花完。

思路：完全背包问题。每种地都是无限的。每块地的花费是a*a,权值是1。所以问题就转化为装满容器n所得到的最小权值。

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

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
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\n",dp[v]);
	}
	return 0;
}