POJ 2642 The Brick Stops Here 0 - 1 가방
부주의:
n (n < = 200) 개의 황동 합금 과 그들의 농도 와 가격 을 드 립 니 다.n 조각 에서 M 조각 을 취하 여 이 M 조각 합금 의 농 도 를 [cMin * M, cMax * M] 이 구간 에서 소비 하 는 가격 이 가장 적 게 되도록 몇 가지 질문 을 드 립 니 다.
여기 상세 해...http://blog.sina.com.cn/s/blog_9b95c19e010192vl.html
디자인 상태 dp [i] [j] [v] 는 i 개 에서 가 치 를 초과 하지 않 는 v 인 물품 j 건 을 산다 고 밝 혔 다.
include<cstdio>
const int INF=999999;
const int MAXN=20000+10;
int w[201],p[201];
int dp[21][MAXN];
int main()
{
int N,M;
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d%d",&w[i],&p[i]);
for(int i=0;i<21;i++)
for(int j=0;j<MAXN;j++)
dp[i][j]=INF;
int maxnum= N >20? 20: N;
dp[0][0]=0;
for(int i=1;i<=N;i++)
{
for(int j=20000;j>=w[i];j--)
for(int k=1;k<=maxnum;k++)
if(dp[k-1][j - w[i] ]!=INF)
dp[k][j] = dp[k][j] < ( dp[k-1][j - w[i] ]+ p[i] )? dp[k][j] : ( dp[k-1][j - w[i] ]+ p[i] );
}
int kase;
scanf("%d",&kase);
for(int ri=0;ri<kase;ri++)
{
int L,R;
scanf("%d%d%d",&M,&L,&R);
L*=M;
R*=M;
int ans=INF;
for(int i=L;i<=R;i++)
if(ans > dp[M][i] )
ans=dp[M][i];
if(ans==INF)
printf("impossible
");
else
printf("%d
",ans);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
