UVa 12589 Learning Vector
1754 단어 vector
사고방식: 먼저 한 가지를 확정하고 선택한 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
",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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Vector & Matrix스칼라 : 하나의 숫자로만 이루어진 데이터 (크기만 있고 방향이 없는 물리량) 벡터 : 여러 숫자로 이루어진 데이터 레코드. 매트릭스 : 벡터가 여럿인 데이터집합 벡터의 크기는 스칼라배를 통해 표현할 수 있다. *내...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
