poj 1976 A Mini Locomotive (dp 2 차원 01 가방)

제목 링크:
http://poj.org/problem?id=1976
제목 의 대의:
어느 역 에는 N 개의 기차 칸 이 있 고 번 호 는 1 ～ N 이 며 각 칸 에는 xi 사람 이 있다.
이 역 에는 세 개의 기관차 가 있 는데, 그들 은 최대 m 개의 객차 (m < = N / 3) 를 끌 수 있 고, 이 m 개의 객차 의 번 호 는 연속 되 어야 한다.이 세 기관 차 는 최대 몇 명 을 끌 수 있 느 냐 고 물 었 다.
생각:
m < = N / 3 이기 때문에 욕심 많은 생각 에 따라 더 많은 사람 을 끌 기 위해 모든 기 차 는 반드시 m 개의 연속 적 인 칸 을 끌 어야 한다.
그 다음 에 특정한 연속 적 인 객차 에 모두 몇 명 이 있 는 지 를 구하 기 위해 접두사 와 예비 처 리 를 할 수 있 습 니 다. 특정한 단락 과 = sum [i] - sum [i - m].
f [i] [j] 는 앞의 i 칸 을 대표 하고 j 개의 기관차 로 끌 면 최대 몇 명 을 끌 수 있 습 니까?
i 번 째 칸 에 대해 현재 이 칸 을 끌 어 당 기 려 면 i 를 마지막 칸 으로 하 는 연속 m 개의 칸 을 같이 당 겨 야 하기 때문에 상태 이동 방정식 은:
f[i][j] = max(f[i-1][j], f[i-m][j-1]+sum[i]-sum[i-m]);
코드:
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<string>
#define MP make_pair
#define SQ(x) ((x)*(x))

using namespace std;
typedef long long int64;

const double PI = acos(-1.0);
const int MAXN = 50010;
const int INF = 0x3f3f3f3f;
int n, m;
int w[MAXN], sum[MAXN];
int f[MAXN][4];


int main(){

    int nCase;
    scanf("%d", &nCase);
    while(nCase--){
        scanf("%d", &n);

        for(int i=1; i<=n; ++i){
            scanf("%d", &w[i]);
            sum[i] = sum[i-1] + w[i];
        }

        scanf("%d", &m);

        memset(f, 0, sizeof(f));
        
        for(int i=m; i<=n; ++i){
            for(int j=3; j>=1; --j){
                f[i][j] = max(f[i-1][j], f[i-m][j-1]+sum[i]-sum[i-m]);
            }
        }
          
        printf("%d
", f[n][3]);
    }
    return 0;
}
데 이 터 를 가 져 오 는 방식 JQ, fetch, ajax, axios 비교
IE 와 FF 에서 select. innerHTML

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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