ZZUOJ-10452 "점"수

3299 단어
이 문제는 일반적인 3차원 dp수 그룹 dp(i)(j)(k), dp(i)(j)|=dp(i-1)(j-1)(k-num[i])를 열어야 한다.그런데 스크롤 수조로 할 수 있어요.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
#include <set>
#include <cstdlib>

using namespace std;
#define INF 1e8
int num[55];
bool dp[55][5050];
int main(){

// freopen("in.txt", "r", stdin);
    int n;

    while(cin >> n){

        int sum = 0;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++){

            scanf("%d", num+i);
            sum += num[i];
        }
        dp[0][0] = true;
        for(int i = 0; i < n; i++)
          for(int j = i+1; j >= 1; j--)
            for(int h = sum; h >= num[i]; h--)
             dp[j][h] |= dp[j-1][h-num[i]]; 

        int m = n / 2;
        int mins = INF, ans;

        for(int h = 0; h <= sum; h++)
            if(dp[m][h]){

            int d = abs(h - sum/2);
            if(mins > d){   
              mins = d;
              ans = h;
            }
           }
        printf("%d %d
", min(ans, sum-ans), max(ans, sum-ans));
    }

    return 0;
}
[알고리즘] 다중 포인터 패턴 설명! (에피소드 1)
VSCode 프로젝트 기반 영구 파일 연결

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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