PKU 1014

JOI予選が近づいてきて,JOI予選の過去問解いてない後輩を煽るためPKUのDP問題解いてます(意味不明)

問題概要

価値が1から6まであるビー玉がある.入力には各々の価値のビー玉の個数が与えられている.二人はビー玉を任意の個数選び,ビー玉の価値を二等分できるかどうか判定する.

 

解法

伝搬させるDP
コメントの部分消しても通ったけど,上手いこと処理してやればもうちょっと早くなるかも.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

const int N = 6;
bool dp[2][120000];

int main() {
    vector<int> v(N);
    for(int testcase = 1; ; testcase++) {
        bool ok = false;
        memset(dp, 0, sizeof dp);

        for(int i = 0; i < N; i++) { scanf("%d", &v[i]); }

        if(accumulate(v.begin(), v.end(), 0) == 0) break;

        int n = 0;
        for(int i = 0; i < N; i++) {
            n += (i + 1) * v[i];
        }

        dp[0][0] = true;

        if(!(n & 1)) {
            n /= 2;
            for(int i = 0; i < N; i++) {
                bool cur = i & 1;
                bool next = (i + 1) & 1;
                for(int j = 0; j <= n; j++) {
                    if(!dp[cur][j]) continue;
                    for(int k = 0; k <= v[i]; k++) {
                        if(j + k * (i + 1) > n) break;
                        //if(dp[next][j + k * (i + 1)]) break; // その先を更新したとしても等差数列になるため更新する必要が無い
                        dp[next][j + k * (i + 1)] = true;
                    }
                }
                memset(dp[cur], 0, sizeof dp[cur]);
                ok |= dp[next][n];
            }
        }

        if(ok) {
            printf("Collection #%d:\nCan be divided.\n", testcase);
        } else {
            printf("Collection #%d:\nCan't be divided.\n", testcase);
        }
        puts("");
    }
}