UVA 10280 Old Wine Into New Bottles(dp 전체 백팩)
Problem C: Old Wine Into New Bottles
Wine bottles are never completely filled: a small amount of air must be left in the neck to allow for thermal expansion and contraction. If too little air is left in the bottle, the wine may expand and expel the cork; if too much air is left in the bottle, the wine may spoil. Thus each bottle has a minimum and maximum capacity.
Given a certain amount of wine and a selection of bottles of various sizes, determine which bottles to use so that each is filled to between its minimum and maximum capacity and so that as much wine as possible is bottled.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of input contains two integers: the amount of wine to be bottled (in litres, between 0 and 1,000,000) and the number of sizes of bottles (between 1 and 100). For each size of bottle, one line of input follows giving the minimum and maximum capacity of each bottle in millilitres. The maximum capacity is not less than 325 ml and does not exceed 4500 ml. The minimum capacity is not less than 95% and not greater than 99% of the maximum capacity. You may assume that an unlimited number of each bottle is available.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Your output should consist of a single integer: the amount of wine, in ml, that cannot be bottled.
Sample Input
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750
Sample Output
250
0
제목: c리터의 술을 주고 n종의 병이 있습니다. 병마다 최소한 min밀리리터와 최대 max밀리리터가 있습니다.그리고min<=0.99max.이 병으로 술을 담고 마지막에 남은 술의 최소 리터를 요구하다.
사고방식:dp, 분명히 가방.그러나 c의 최대 100W를 리터로 환산하면 10E가 된다.과감하게 시간을 초과할 수 있다.이때 제목을 살펴보면 발견할 수 있다.
만약 우리가 K병으로 술을 담는다면그러면 좌우 구간의 길이가 점점 커져 결국 중합된다.그래서 주량이 일정한 상한선에 도달하면 틀림없이 완전히 담을 수 있을 것이다.추측해 보자: 중합을 설정할 때 k병을 담았는데 이렇게 있다.k*max>=(k+1)*min, k>=min/(max-min)를 풀고 주량 x>=k*min일 때 반드시 다 담을 수 있다. 그러면 x>=min*min/(max-min)이 있다.
코드:
#include <stdio.h>
#include <string.h>
const int INF = 2000000000;
int t, c, n, i, j, dp[500000], m, v[4555], vis[4555], limit;
struct P {
int min;
int max;
} p[105];
int max(int a, int b) {return a > b ? a : b;}
int min(int a, int b) {return a < b ? a : b;}
int main() {
scanf("%d", &t);
while (t --) {
limit = INF;
scanf("%d%d", &c, &n);
c *= 1000;
for (i = 0; i < n; i ++) {
scanf("%d%d", &p[i].min, &p[i].max);
limit = min(limit, p[i].min * p[i].min / (p[i].max - p[i].min));
}
if (c >= limit) {
printf("0
");
if (t)
printf("
");
continue;
}
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
m = 0;
for (i = 0; i < n; i ++)
for (j = p[i].min; j <= p[i].max; j ++)
if (!vis[j]) {
vis[j] = 1;
v[m ++] = j;
}
for (i = 0; i < m; i ++) {
for (j = v[i]; j <= c; j ++) {
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
}
}
printf("%d
", c - dp[c]);
if (t)
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.