首页 > 代码库 > Learning Vector
Learning Vector
题目链接
- 题意:
n个向量,选k个首位相连,求与x轴的面积最大值 - 分析:
首先明白:对于给定的一些向量,按照斜率从大到小排序的面积是最大的,那么,对输入的排序就是显而易见的了
考虑当前的状态,需要知道之前的高度才能表示当前状态。显然,对于高度相同的状态还应该和已经用的向量数有关,所以状态有两个
转移就是一个简单的数学公式,没什么说的
const int maxn = 100; struct Node { int x, y; int operator< (const Node& rhs) const { return y * rhs.x > x * rhs.y; } } ipt[60]; int dp[2][2600][60]; int main() { int T, n, m; RI(T); FE(kase, 1, T) { REP(i, 2) REP(j, 2600) REP(k, 60) dp[i][j][k] = -100000000; RII(n, m); int maxh = 0; REP(i, n) { RII(ipt[i].x, ipt[i].y); maxh += ipt[i].y; } sort(ipt, ipt + n); int cur = 0; dp[cur][0][0] = 0; REP(i, n) { int x = ipt[i].x, y = ipt[i].y; cur ^= 1; FE(j, 0, maxh) FE(k, 0, m) dp[cur][j][k] = dp[cur ^ 1][j][k]; FE(j, 0, maxh - y) FE(k, 0, m - 1) dp[cur][j + y][k + 1] = max(dp[cur][j + y][k + 1], dp[cur ^ 1][j][k] + j * x * 2 + x * y); } int ans = 0; FE(i, 0, maxh) ans = max(ans, dp[cur][i][m]); printf("Case %d: %d\n", kase, ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。