首页 > 代码库 > HDU5100Chessboard(数论)
HDU5100Chessboard(数论)
HDU5100Chessboard(数论)
题目链接
题目大意:用k?1的瓷砖区铺n?n的矩形,问能铺上的最大的面积。
解题思路:这题没有直接得出结论:l = n%k, ans = max[(n^2 - l^2), (n^2 - (k - l)^2)],但是在画的过程中发现了,最好的情况就只有两种铺法,要不按照贪心的策略来铺,直到铺不下为止。或者是一圈一圈的铺,铺完一圈后最后还会剩下一个矩形,然后再递归子问题,每个子问题都是返回面积最大的。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int find (int n, int k) {
if (n < k)
return 0;
int mul = n / k;
int mod = n % k;
return (mul * n + mod * mul) * k;
}
int solve (int n, int k) {
int tmp1 = find(n, k), tmp2 = 0;
if (n > k && n % k)
tmp2 = solve(n - 2 * (n % k), k) + 4 * (n / k) * (n % k) * k;
return max(tmp1, tmp2);
}
int main () {
int T, N, K;
scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &N, &K);
printf ("%d\n", solve(N, K));
}
return 0;
}
HDU5100Chessboard(数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。