POJ 2392 스페이스 엘리베이터 [DP 멀 티 백 팩]
n 가지 벽돌 을 주 고 모든 벽돌 은 c 개 이 며 높이 는 w 이 며 h 높이 에서 사용 할 수 있 습 니 다.
어떻게 누적 하면 총 높이 를 가장 높 일 수 있 는 지 물 었 다.
생각:
h 고도 의 제약 이 없다 면 분명히 전부 더 하면 된다.
dp 로 해결 합 니 다. 모든 높이 j 는 상태 입 니 다.그래서 본질은 가방 문제 예요.
각 벽돌 은 유한 개 이기 때문에 다 중 가방 입 니 다.이 진 으로 시간 을 최적화 하 다.
그러나 h 고도 제약 문제 로 인해 모든 상태 j 는 고도 제약 h > = j 의 벽돌 과 관련 이 있 을 수 있 습 니 다.
그 러 니까 h 높이 에서 작은 것 부터 큰 것 까지 정렬 한 다음 에 dp.
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<algorithm>
#define llong long long
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
#define Abs(a) ((a)>0?(a):-(a))
#define Mod(a,b) (((a)-1+(b))%(b)+1)
using namespace std;
int n,m;
const int N=7005;
const int M=40005;
const int inf=99999999;
int dp[M];
struct Node
{
int w,h;
}node[N];
bool cmp(const Node &a,const Node &b)
{
return a.h<b.h;
}
void solve()
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=node[i].h;j>=node[i].w;j--)
{
dp[j]=Max(dp[j],dp[j-node[i].w]+node[i].w);
}
}
int ans=0;
for(int i=1;i<=node[n].h;i++)
ans=Max(ans,dp[i]);
printf("%d
",ans);
}
int main()
{
int tmp,a,b,c;
n=0;
scanf("%d",&tmp);
for(int i=1;i<=tmp;i++)
{
scanf("%d%d%d",&a,&b,&c);
for(int j=1;c;j*=2)
{
n++;
node[n].h=b;
if(j<=c)
{
node[n].w=a*j;
c-=j;
}
else
{
node[n].w=a*c;
c=0;
}
}
}
sort(node+1,node+1+n,cmp);
solve();
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
