首页 > 代码库 > URAL 1073 Square Country(DP)
URAL 1073 Square Country(DP)
Square Country
大意: 买一块边长为 a 的正方形地需要的钱数是 a^2, 现在输入N为钱的数目,求最少购买地的块数可以凑够N。
思路:DP,由背包思想推出来的dp[i] = min(dp[i], dp[j-i*i]+1); 方块都是由正方形组成的,所以是i*i,循环的时候也是i*i。
#include <stdio.h> #define min(a, b) ((a) > (b) ? (b) :(a)) int n; int dp[60005]; int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i){ dp[i] = i; } for(int i = 1; i*i <= n; ++i){ for(int j = i*i; j <= n; ++j){ dp[j] = min(dp[j], dp[j-i*i]+1); } } printf("%d\n", dp[n]); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。