Educational Codeforces Round 61 (Rated for Div. 2) E. Knapsack

1732 단어
매우 고전적인 dp문제입니다. 1부터 8까지의 최대 공약수는 840이고 그 어떠한 수의 배수와 중 840의 배수도 함께 계산할 수 있기 때문에 저는 840*8의 값(각 숫자(1-8)의sum%840의 총계)을 통계하고 나머지는 840의 배수 dp[i][j]가 i위를 논의했고 각 숫자가 j로 남는 상황을 대표합니다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
typedef long long ll;

ll a[10];
ll dp[10][8400];

int main() {
    ll w;
    while(~scanf("%lld", &w)) {
        for(int i = 0; i < 8; ++i) {
            scanf("%lld", &a[i]);
        }
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for(int i = 0; i < 8; ++i) {
            for(int j = 0; j < 8400; ++j) {
                if(dp[i][j] == -1) continue;
                int edge = min(1ll * 840 / (i + 1), a[i]); 
                for(int k = 0; k <= edge; ++k) {
                    dp[i + 1][j + k * (i + 1)] = max( dp[i + 1][j + k * (i + 1)], dp[i][j] + (a[i] - k) / (840 / (i + 1)));
                }
            }
        }

        ll ans = -1;
        for(int i = 0; i < 8400; ++i) {
            if(dp[8][i] == -1 || i > w) continue;
            ans = max(ans, i + min( (w - i) / 840, dp[8][i]) * 840);
        }
        printf("%lld
", ans); } return 0; }

좋은 웹페이지 즐겨찾기