2.3.3 동태 계획 - 진급 POJ 1065 1631 3666 2392 2184

18836 단어 동적 계획poj프로 그래 밍 경연 에 도전 하 다.
POJ1065
http://poj.org/problem?id=1065
제목
묘사 하 다.
C. 작은 나무 막대 가 있 는데 그들의 길이 와 품질 은 모두 알 고 있다. 한 기계 가 이런 나무 막대 기 를 처리 해 야 한다. 기계 가 작 동 할 때 한 단위 의 시간 이 필요 하 다. 만약 에 i + 1 개의 나무 막대 의 무게 와 길이 가 모두 i 가 처리 하 는 나무 막대 보다 크 면 시간 을 소모 하지 않 을 것 이다. 그렇지 않 으 면 한 단위 의 시간 을 소모 해 야 한다.서둘러 데 이 트 를 하 러 갔 기 때문에 C 샤 오 카 는 가장 짧 은 시간 안에 나무 막대 기 를 다 처리 하고 싶 었 다. 그 에 게 어떻게 해 야 하 는 지 알려 줄 수 있 습 니까?
입력
첫 번 째 줄 은 정수 T 로 입력 데이터 가 모두 T 그룹 임 을 나타 낸다.각 조 의 테스트 데이터 의 첫 줄 은 하나의 정수 N (1 & lt; N & gt; = 5000) 으로 N 개의 나무 막대 가 있다 는 것 을 나타 낸다.다음 줄 은 각각 N 개의 나무 막대기 의 L, W (0 < L, W < = 10000) 를 입력 하고 빈 칸 으로 나 누 어 나무 막대기 의 길이 와 품질 을 표시 합 니 다.
출력
이 나무 막대 들 을 처리 하 는 가장 짧 은 시간.
샘플 입력
3 5 4 9 5 2 2 1 3 5 1 4 3 2 2 1 1 2 2 3 1 3 2 2 3 1
샘플 출력
2 1 3
사고의 방향
문 제 는 확실히 좀 더 생각해 야 한다. 이 문제 의 요 구 는 모든 stick 를 x 개의 하강 하지 않 는 서브 시퀀스 (Ai < = Ai + 1) 로 나 눈 다음 에 문 제 는 x 의 최소 치 를 구 하 는 것 이다.x 의 최소 값 은 l 에 따라 정렬 한 후에 stick 는 w 의 최 장 하강 서브 시퀀스 의 길이 L 와 같다.증명 은 다음 과 같 습 니 다. 만약 에 x < L, 먼저 stick 에서 최 장 하강 서브 시퀀스 L 을 꺼 내 고 가 져 간 요 소 는 크기 가 같은 '빈 구멍' 을 남 긴 다음 에 남 은 요소 와 빈 구멍 을 x 개 로 나 누 어 하위 서열 을 낮 추 지 않 습 니 다.이 어 최 장 하강 서브 시퀀스 L 의 L 개 요 소 를 이 L 개의 빈 구멍 에 다시 넣 었 다.x < L 이기 때문에 비둘기 우리 원리 에 따라 반드시 두 개 또는 두 개 이상 의 하강 자 서열 L 중의 요소 (b > a) 가 순서대로 같은 하강 자 서열 (a < = b) 에 놓 여 모순 이 발생 한다 (둘 은 원래 같은 효 과 를 가 져 야 한다).문 제 는 최 장 하강 서브 시퀀스 의 길이 L 로 요약 된다. 만약 에 정의 하면 dp [i]: = 길 이 는 i + 1 의 하강 서브 시퀀스 에서 마지막 요소 의 최대 값 이 고 업데이트 시 이분법 으로 찾 으 며 복잡 도 는 O (nlogn) 이다.이 문제 에 대한 더욱 상세 한 수학 분석 은 박문: poj 1065 – Wooden Sticks – Dilworth 정리 체인 - 반 사슬 - Dilworth 정리
코드
Source Code

Problem: 1065       User: liangrx06
Memory: 300K        Time: 16MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 5000;
const int INF = 0x3f3f3f3f;

struct Stick {
    int l, w;
};

bool cmp(const Stick& a, const Stick b)
{
    return (a.l != b.l) ? (a.l > b.l) : (a.w > b.w);
}

int main(void)
{
    int t, n;
    Stick s[N];
    int dp[N];

    cin >> t;
    while (t--) {
        cin >> n;
        fill(dp, dp+n, INF);
        for (int i = 0; i < n; i ++)
            scanf("%d%d", &s[i].l, &s[i].w);
        sort(s, s+n, cmp);
        for (int i = 0; i < n; i ++) {
            *lower_bound(dp, dp+n, s[i].w) = s[i].w;
        }
        printf("%d
", lower_bound(dp, dp+n, INF) - dp);
    }

    return 0;
}

POJ1631
http://poj.org/problem?id=1631
제목
새로 온 인턴 이 노선 을 엉망 으로 만 들 었 어!그림 과 같이 원래 좌우 포트 는 순서대로 연결 해 야 한다.지금 은 일부 선 로 를 절제 해서 어떤 노선 도 교차 하지 않 게 한다.당신 이 프로그램 을 써 서 마지막 에 몇 개의 노선 이 남 았 는 지 계산 하 기 를 바 랍 니 다.
사고의 방향
전형 적 인 최 장 불 하강 서브 시퀀스 LIS.O (n ^ 2) 의 방법 도 있 고 O (nlogn) 의 방법 도 있 습 니 다. 여기 서 저 는 O (nlogn) 의 기본 적 인 사 고 를 사 용 했 습 니 다. 기본 적 인 사 고 는 tot = 1 (가장 길 고 하위 서열 이 떨 어 지지 않 기 때문에 최 악의 경우 1 개의 데이터 가 있 습 니 다) 입 니 다. 그리고 한 개의 데이터 x 를 읽 을 때마다 배열 a [] 에서 2 점 으로 찾 아 가장 작은 x 보다 큰 a [i] 를 찾 아 a [i] = x 를 교체 합 니 다.찾 지 못 하면 x 를 a [] 의 마지막, 즉 tot + + 에 삽입 합 니 다.마지막 tot 가 바로 원 하 는 것 입 니 다.알고리즘 의 시간 복잡 도 는 2 분 에 O (logn) 를 찾 고 모두 n 개의 데이터 가 있 기 때문에 O (n * logn) 입 니 다.STL 의 lower 이용 하기bound 함 수 는 손 으로 쓴 2 점 을 대체 하여 찾 을 수 있 고 계수 변 수 를 절약 할 수 있 습 니 다.
코드
Source Code

Problem: 1631       User: liangrx06
Memory: 552K        Time: 125MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 40000;
const int INF = 0x3f3f3f3f;

int main(void)
{
    int t, n;
    int a[N];
    int dp[N];

    cin >> t;
    while (t--) {
        cin >> n;
        fill(dp, dp+n, INF);
        for (int i = 0; i < n; i ++) {
            scanf("%d", &a[i]);
            *lower_bound(dp, dp+n, a[i]) = a[i];
        }
        printf("%d
", lower_bound(dp, dp+n, INF) - dp);
    }

    return 0;
}

POJ3666
http://poj.org/problem?id=3666
제목
농부 존 은 가능 한 한 평탄 한 길 을 만 들 고 싶 어 한다 (높이 가 증가 하지 않 거나 감소 하지 않 는). 길의 모든 해발 은 A 이다.i, 수리 후 Bi, 소비 | Ai – B_i | 최소 비용 을 구하 세 요.
사고의 방향
이 문 제 는 증가 하지 않 는 것 과 감소 하지 않 는 것 두 가지 상황 이 유사 하기 때문에 우 리 는 여기 서 감소 하지 않 는 상황 만 을 고려한다.우선 최종 수정 후 Bi 또는 앞의 숫자 와 같 거나 뒤의 숫자 와 같 아야 수 정 량 이 가장 적다.그래서 Bi 의 출처 는 원래 수열 의 수 일 수 밖 에 없다.우 리 는 먼저 원수 열 에 따라 정렬 하여 원소 의 크기 관 계 를 확정 하고 대응 번 호 는 b [i] 이다.DP 배열 의 구체 적 인 표현 은 dp [i] [j] 는 앞의 i 개 요 소 를 고려 하고 마지막 요 소 는 서열 에서 j 작은 요소 의 최 적 화 된 dp [i] [j] = MIN (dp [i - 1] [k]) + abs (a [i] - a [p [j]), (0)
코드
Source Code

Problem: 3666       User: liangrx06
Memory: 292K        Time: 47MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 2000;
const int INF = INT_MAX/2;

int n;
int a[N], b[N];
int dp[2][N+1];

int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    memcpy(b, a, sizeof(a));
    sort(b, b+n);

    fill(dp[0], dp[0]+1+n, INF);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int preMinCost = dp[(i-1)&1][0];
        for (int j = 0; j < n; j++) {
            preMinCost = min(preMinCost, dp[(i-1)&1][j]);
            dp[i&1][j] = preMinCost + abs(b[j] - a[i-1]);
        }
    }
    cout << *min_element(dp[n&1], dp[n&1]+n) << endl;

    return 0;
}

POJ2392
http://poj.org/problem?id=2392
제목
k 종의 돌 이 있 는데 높이 는 hi 이다. ai 를 초과 하지 않 는 높이 에서 이런 돌 은 놓 을 수 있다. ci 종의 이 돌 이 있 는데 이 돌 들 이 놓 을 수 있 는 최고 높이 를 구한다.
사고의 방향
제한 조건 이 있 는 멀 티 백 팩 입 니 다. 우선 제한 조건 을 정렬 처리 하고 돌 을 ai 크기 로 정렬 해 야 합 니 다. 그 다음 에 하나의 표준 멀 티 백 팩 입 니 다. 그 다음 에 이 문제 의 해법 은 '도전' 책의 P62 - 63 의 다 중 부분 과 문제 와 거의 같 습 니 다. 그리고 제 또 다른 블 로그 인 '도전 프로 그래 밍 경연 대회' 를 참고 하 실 수 있 습 니 다.2.3.2 동적 계획 - 최적화 전달 POJ 1742 3046 3181 중의 POJ 1742 문제 에 대한 상세 한 설명.
코드
Source Code

Problem: 2392       User: liangrx06
Memory: 404K        Time: 63MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int K = 400;
const int A = 40000;

struct Block {
    int h, a, c;
};

bool cmp(Block x, Block y)
{
    return x.a < y.a;
}

int main(void)
{
    int k;
    Block b[K];
    int dp[A+1];
    cin >> k;
    for (int i = 0; i < k; i ++)
        scanf("%d%d%d", &b[i].h, &b[i].a, &b[i].c);
    sort(b, b+k, cmp);

    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i < k; i ++) {
        for (int j = 0; j <= b[i].a; j ++) {
            if (dp[j] >= 0)
                dp[j] = b[i].c;
            else if (j < b[i].h || dp[j-b[i].h] <= 0)
                dp[j] = -1;
            else
                dp[j] = dp[j-b[i].h] - 1;
        }
    }
    int m;
    for (m = b[k-1].a; m >= 0; m --) {
        if (dp[m] >= 0) break;
    }
    printf("%d
", m);

    return 0;
}

POJ2184
http://poj.org/problem?id=2184
제목
일부 젖소 들 은 일정한 s 값 과 f 값 을 가지 고 있 는데 이런 값 은 플러스 마이너스 가 있 고 마지막 으로 s 의 것 과 마이너스 가 아 닌 f 의 것 과 마이너스 가 아 닌 상황 에서 s + f 의 최대 치 를 확보한다.
사고의 방향
딱 봐 도 01 배낭 이지 만 제목 의 제한 조건 은 처리 하기 어 려 운 것 같다. 이 문제 의 관건 은 두 가지 가 있다. 하 나 는 smartness 를 비용 으로 보고 funness 를 가치 로 보고 01 가방 으로 바 꾸 는 것 이다. 다른 하 나 는 마이너스 에 대한 처리 이 고 하나의 shift 를 도입 하여 '0' 을 표시 하 는 것 이다. 이곳 의 shift 는 반드시 모든 smartness 의 절대 치보다 크 고, 다른 하 나 는 cost [] 를 옮 겨 다 니 고 있다.경우 에 cost [i] > 0, 분명히 열 린 배열 의 최대 치 maxm 에서 아래로 줄 어 들 기 시 작 했 습 니 다. cost [i] < 0 이면 0 (shift 가 아 닌 0) 에서 위로 증가 하기 시 작 했 습 니 다. 0 이상 이면 생각 하기 쉽 습 니 다. 0 이하 의 경우 에는 잘 생각해 야 합 니 다. 소 한 마리 만 있 는 것 을 고려 하면 smartness 는 - x (x > 0), funness 는 y (y > 0) 입 니 다. dp [shift] 를 고려 해 야 하기 때 문 입 니 다.초기 값 은 0 이 고, 다른 dp [] 의 초기 값 은 마이너스 입 니 다. 따라서 dp [shift - (- x)] + y > dp [shift], 즉 dp [x] 는 dp [shift - (- x)]] + y 즉 y (dp [x] = max (dp [shift - (- x)] + y, dp [shift]) 로 부 여 됩 니 다. x 는 shift 보다 작 기 때문에 마지막 에 최대 값 을 옮 겨 다 닐 때 이 값 은 옮 겨 다 니 지 않 습 니 다. 앞 에 소 가 있 는 것 을 고려 하면 dp [shift + x] = y (x > 0, y > 0)현재 - a b (a > 0, b > 0) 인 소 한 마리 가 나 타 났 습 니 다. 그러면 dp [shift + X - a] 는 dp [shift + x - a - (- a)] + b = dp [shift + x] + b = y + b 로 부 여 됩 니 다. 마지막 으로 옮 겨 다 닐 때 마지막 소 와 x - a + y + b 를 취하 지 않 으 면 x + y 로 부 여 됩 니 다. 따라서 최대 치 는 누가 b - a 의 플러스 인지 에 달 려 있 습 니 다. 다시 말 하면 이것 은 문제 의 요 구 를 만족 시 키 는 방법 이기 때문에 cost [i] 에서< 0 시 0 부터 위로 증가 합 니 다.
그리고 제 가 하 는 과정 에서 memcpy (crt, nxt, sizeof (nxt)) 는 제대로 된 배열 복사 효 과 를 얻 지 못 했 습 니 다. 오 랜 시간 을 찾 아 보 니 이 말 에 문제 가 생 겼 습 니 다. 그리고 인터넷 에서 memset 의 용법 을 찾 아 보 았 지만 문제 가 발견 되 지 않 았 습 니 다. 앞으로 memcpy 함 수 를 조심해 야 할 것 같 습 니 다. 이 문제 에 관 한 다른 분석 은 블 로그: poj 2184 Cow Exhibition 01 가방 변형 을 참고 할 수 있 습 니 다.
코드
Source Code

Problem: 2184       User: liangrx06
Memory: 1804K       Time: 266MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100;
const int M = 1000;
const int MAX = M*N;
const int INF = 2*MAX+1;

int n;
int s[N+1], f[N+1];
int dp[2][MAX*2+1];

int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%d%d", &s[i], &f[i]);

    int *crt = dp[0], *nxt = dp[1];
    fill(nxt, nxt+MAX*2+1, -INF);
    nxt[MAX] = 0;
    for (int i = 0; i < n; i ++) {
        //memcpy(crt, nxt, sizeof(nxt));
        for (int j = 0; j <= 2*MAX; j ++)
            crt[j] = nxt[j];
        for (int j = 0; j <= 2*MAX; j ++) {
            int j0 = j-s[i];
            if (j0 >= 0 && j0 <= 2*MAX && crt[j0] != -INF) {
                nxt[j] = max(nxt[j], crt[j0]+f[i]);
            }
        }
    }
    int ans = 0;
    for (int j = 2*MAX; j >= MAX; j --) {
        if (nxt[j] >= 0)
            ans = max(ans, nxt[j]+j-MAX);
    }
    printf("%d
", ans);

    return 0;
}
Pow
HDU 4966 GGS - DDU 최소 트 리 맵

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage