UVa 10280 올 드 와인 인 투 뉴 병 (가지치기 + 완전 가방)
5548 단어 wine
L 리터 의 술 을 주 고 n 개의 술병 이 있 으 며 모든 술병 은 최대 용량 과 최소 용량 이 있 으 며 술병 의 개 수 는 제한 이 없다.
최대 몇 밀리리터 의 술 이 남 았 는 지 물 었 다.
생각:
http://www.cnblogs.com/staginner/archive/2011/12/07/2279783.html
이 문 제 는 최 적 화 된 가지치기 에 사용 되 었 고 위의 블 로 그 는 물품 에 대한 처리 도 매우 적절 하 다.
문 제 를 다 풀 고 나 면 바람 을 쐬 는 것 처럼 뒷맛 이 끝 이 없다.
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm>
using namespace std; const int MAXL = 450000; const int MAXD = 4600; const int MAXN = 110; int dp[MAXL], v[MAXD]; bool vis[MAXD]; int cmax[MAXN], cmin[MAXN]; int L, n; int solve() { int limit = INT_MAX; for (int i = 0; i < n; ++i) limit = min(limit, cmin[i]*cmin[i]/(cmax[i]-cmin[i])); if (limit < L) return 0; int m = 0; memset(vis, false, sizeof(vis)); for (int i = 0; i < n; ++i) for (int j = cmin[i]; j <= cmax[i]; ++j) if (!vis[j]) vis[j] = true, v[m++] = j; memset(dp, 0, sizeof(dp)); for (int i = 0; i < m; ++i) for (int j = v[i]; j <= L; ++j) dp[j] = max(dp[j], dp[j-v[i]] + v[i]); return L - dp[L]; } int main() { int cases; scanf("%d", &cases); while (cases--) { scanf("%d %d", &L, &n); L *= 1000; for (int i = 0; i < n; ++i) scanf("%d %d", &cmin[i], &cmax[i]); printf("%d
", solve()); if (cases) printf("
"); } return 0; }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Wine에서 MIDITrail을 움직여보십시오.(여름방학 기획 4/20) MIDITrail 는 MIDI 시퀀스를 3D 공간상에 가시화할 수 있는 MIDI 플레이어. MS-Windows/OSX/iOS 대응이지만 Linux에서도 Wine에서 움직일 수 있습니다. 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
