POJ - 2144: Cow Exhibition - 01 가방, 양수 처리, 소계

클릭 하여 원제 로 이동
최근 며칠 동안 줄곧 dp 를 쓰 고 있 습 니 다. 매일 Cows 입 니 다. 산 에 올 랐 다가 젖 을 짜 고 꽃 을 훔 쳤 다가 운전 을 했 는데 오늘 또 지능 이 마이너스 인 orz 를 보 았 습 니 다.

제목
N N 그룹 데 이 터 를 지정 합 니 다. 각 그룹의 데 이 터 는 s i, f i s 를 포함 합 니 다.i,f_i. si, fi, 데 이 터 는 플러스 마이너스 가 있 고 그 중의 일부 그룹 을 선택 하여 각 그룹의 ＞ s, ＞ f \ sum s, \ sum f ＞ s, ＞ f 의 합 이 각각 0 보다 큰 전제 에서 모든 데이터 의 합 과 ＞ s + ＞ f \ sum s + \ sum f ＞ s + \ sum f ＞ s + ＞ f 가 가장 크다. *
이 문 제 는 초보 자 에 게 너무 잔인 해 서 는 안 된다. 그러나 한참 동안 AC 를 사용 한 후에 감명 이 깊 었 고 블 로 그 를 써 서 인상 을 깊 게 하 는 주요 난점 이 었 다.

추상 적 이어서 초보 자 에 게 는 0 - 1 가방 을 직접 연상 하기 가 쉽 지 않 을 것 이다.

데이터 의 양음 문 제 는 음수 의 처리 가 매우 중요 하 다.

자, 내 려 와 서 문 제 를 풀 겠 습 니 다.
전역 변수 정의

#define ll int
#define Max 105
#define inf 1000*100*2//100 cow     1000，    100*1000

음수 가 가 져 온 영향 을 처리 하기 위해 서 는 배열 이 비교적 큰 size 를 열 어야 하 는데 어떻게 고려 해 야 합 니까?다행히 데이터 범위 가 크 지 않 아서 주로 좌표 축 을 사용 하여 전체적으로 오른쪽으로 이동 하 는 사고 방향 은 최대 100 마리 의 소 가 있 습 니 다. 모든 소의 지능 범 위 는 - 1000 – 1000 사이 에 있 습 니 다. 그러면 그들의 총 화 는 - 100000 – 100000 이 구간 에 떨 어 진 것 입 니 다. 즉, 우리 의 dp 는 20000 이렇게 커 야 합 니 다.정 수 는 100000 부터 계산 을 시작 하여 음 수 를 0 - 100000 의 위치 로 옮 겼 다.
초기 화 를 기억 하 세 요. 음수 초기 화 는 소홀히 해 서 는 안 됩 니 다.

	for (ll i = 0; i < 2 * inf; i++) dp[i] = -inf;
	dp[inf] = 0;

memset 에 bug 가 있 는 것 같 습 니 다.
포인트 가 왔 습 니 다. 0 - 1 가방 의 변형.

s [i] > 0 s [i] > 0 s [i] > 0 이것 이 정상 적 인 가방 입 니 다. 간소화 한 후의 형식 은 뒤에서 앞으로 업데이트 하 는 것 입 니 다. i f if 문 구 는 나중에 다시 말 합 니 다.주 의 는 [0, 2 * 8727, i n f] [0, 2 * inf] [0, 2 * 8727, inf] 구간 에서 모두 가방 을 진행 해 야 합 니 다. 왜냐하면 d p [] dp [] dp [] 는 반드시 마이너스 로 고려 해 야 하기 때 문 입 니 다. 단일 s [i] s [i] s [i] s [i] 는 플러스 마이너스 입 니 다.

s [i] < 0 s [i] < 0 s [i] < 0 조금 특별 합 니 다. 만약 에 품질 s [i] = − 4 s [i] = - 4 s [i] = − 4, 현재 사용 가능 한 품질 은 11 입 니 다. 그러면 우 리 는 이 c o w cow cow 를 선 택 했 습 니 다. 이것 은 무엇 을 의미 하 는 것 입 니까? 그 를 선택 하 는 데 - 4 의 대 가 를 썼 습 니 다. 만약 에 우리 가 사용 할 수 있 는 품질 을 선택 하면 1 - (- 4) = 5 (총 품질 - 대가), 1 위 치 를 갱신 하고 5 위치의 요 소 를 사 용 했 습 니 다.그래서 마 이 너 스 는 이동 한 후에 업 데 이 트 됩 니 다

.

	for (ll i = 0; i < n; i++) {
     //          
		//          ，  ！！！
		//          0-1  ，       ，       dp      ，    
		//     ，      
		/*
			dp[i]   ，     i ，         ，i     ，dp[i]    
		*/
		if (s[i] > 0) {
     
			for (ll j = 2 * inf - 1; j >= s[i]; j--) {
     //0-1          
				if (dp[j - s[i]] > -inf)//        j-s[i]   
					dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
			}
		}
		else {
     
			for (ll j = 0; j < 2 * inf + s[i]; j++) {
     
				if (dp[j - s[i]] > -inf)
					//        ，     dp[j-s[i]]   element
					dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
			}
		}
	}

사실 모든 젖소 의 핵심 문 제 는 선택 과 선택 에 있다. 만약 에 ∑ f = j \ sum f = j ∑ f = j 를 선택 할 때 i 소 를 선택한다 면 선택 한 이 젖소 의 s [i] s [i] s [i] 를 빼 면 나머지 j - s [i] j - s [i] j - s [i] 도 반드시 존재 해 야 한다. 즉, 이미 선택 한 젖소 ∑ f \ sum f ∑ f 를 통 해 계산 할 수 있 는 값 이다. 계산 할 수 있 는 이상,그럼 분명히 업 데 이 트 했 을 거 야, 즉 조건 > - i n f > - inf > - inf.
자, 즐 거 운 A. C. AC. 쓰 는 과정 에서 POJ 의 데이터 가 보통 물이 아니 라 는 것 을 알 게 되 었 습 니 다. 코드 [] [] 가 잘못 확대 되 었 는데 AC ORZ 라 니.
나중에 사용 할 수 있 도록 마지막 으로 전체 코드 를 동봉 합 니 다.

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define ll int
#define Max 105
#define inf 1000*100*2//100 cow     1000，    100*1000
#define p pair
ll n, s[Max], f[Max], ans = 0;
ll dp[2 * inf];

int main() {
     
	cin >> n;
	// s[i]   ，f[i]   ，  0-1     。
	for (ll i = 0; i < n; i++) {
      cin >> s[i] >> f[i]; }
	for (ll i = 0; i < 2 * inf; i++) dp[i] = -inf;
	dp[inf] = 0;
	for (ll i = 0; i < n; i++) {
     //          
		//          ，  ！！！
		//          0-1  ，       ，       dp      ，    
		//     ，      
		/*
			dp[j]   ，     i ，         ，i     ，dp[i]    
		*/
		if (s[i] > 0) {
     
			for (ll j = 2 * inf - 1; j >= s[i]; j--) {
     //0-1          
				if (dp[j - s[i]] > -inf)//        j-s[i]   
					dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
			}
		}
		else {
     
			for (ll j = 0; j < 2 * inf + s[i]; j++) {
     
				if (dp[j - s[i]] > -inf)
					//        ，     dp[j-s[i]]   element
					dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
			}
		}
	}
	for (ll i = inf; i < 2 * inf; i++) {
     
		if (dp[i] > 0)//  f[i]     0 ,          
			ans = max(ans, dp[i] + i - inf);
		/*
		           i-inf，        i     ，dp[i]  i         ，
		             ，    dp   dp[i-1]->dp[i]     ，    ，   
		-inf  ，         ，
		*/
	}
	cout << ans << endl;
}