首页 > 代码库 > UVa 12589 Learning Vector
UVa 12589 Learning Vector
题意:有n个向量(0 <= x,y <= 50),选出其中的K个(n,k <= 50) 围成的面积最大为多少?
思路:先确定一点,对于选出的k个向量,按斜率从大到小的顺序摆放,面积最大。(不然会损失几个平行四边形的面积) 然后DP , DP[id][cur][height] 分别表示前id个向量,已经选出了cur个向量,高度为height的最大面积。面积计算公式为 x0*y0 + 2*x1*y0+x1*y1 + 2*x2*(y0+y1)........用记忆化搜索注意初始化的优化!
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 50+10; const int INF = 1e9; int dp[maxn][maxn][2600]; int vis[maxn][maxn][2600]; struct Vector{ int x,y; Vector(int x = -1,int y = -1):x(x),y(y){} friend bool operator < (Vector a,Vector b) { return a.y*b.x > a.x*b.y; } }; Vector V[maxn]; int n,k; int plu; int ans; int dfs(int id,int cur,int hi) { if(cur==k) return 0; if(id==n) return -INF; if(vis[id][cur][hi] == plu) return dp[id][cur][hi]; vis[id][cur][hi] = plu; int ans = 0; if(ans < dfs(id+1,cur,hi)) ans = dfs(id+1,cur,hi); if(ans < dfs(id+1,cur+1,hi+V[id].y)+2*V[id].x*hi+V[id].x*V[id].y) ans = dfs(id+1,cur+1,hi+V[id].y)+2*V[id].x*hi+V[id].x*V[id].y; return dp[id][cur][hi] = ans; } void input() { ans = 0; scanf("%d%d",&n,&k); int sum = 0; for(int i = 0; i < n; i++) { scanf("%d%d",&V[i].x,&V[i].y); sum += V[i].y; } sort(V,V+n); } void solve() { plu++; ans = dfs(0,0,0); printf("%d\n",ans); } int main() { int ncase,T=1; cin >> ncase; memset(vis,0,sizeof vis); plu = 1; while(ncase--) { input(); printf("Case %d: ",T++); solve(); } return 0; }
UVa 12589 Learning Vector
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。