题目地址:http://poj.org/problem?id=1014

题目大意

有价值为$1,2,3,4,5,6$的六种石头,个数分别为$n_1, n_2, n_3, n_4, n_5, n_6$,试问能否平分这些石头(使平分后价值一样)。

思路

首先计算出总价值$V$,若为奇数肯定不能平分。然后计算出能否利用这些石头凑成$V/2$即可。

设$dp[i+1][j]$为前$i$个石头凑成的价值为$j$时最多能剩下多少个石头(不能凑成为$-1$)

$$ dp[i+1][j] = \begin{cases} n[i] & dp[i][j] >= 0 & (前i-1个数能凑成j) \\ -1 & dp[i+1][j-i] <= 0="" &(否则若前i个数也不能凑成j则无法凑成,第i个数已用完)\\="" dp[i+1][j-i]-1="" &="" dp[i+1][j-i]=""> 0 & (否则利用第i个数来凑成) \end{cases}$$

AC代码

/*************************************************************************
    > File Name: 1014.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-16 五 20:11:19 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int a[7];
int Value;
int dp[20000*6 + 5];
int Case = 1;

void solve() {
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    printf("Collection #%d:\n", Case++);
    for(int i=1; i<=6; ++i) {
        for(int j=0; j<=Value; ++j) {
            if(dp[j] >= 0) dp[j] = a[i];
            else if(j < i || dp[j-i] <= 0) dp[j] = -1;
            else dp[j] = dp[j-i] - 1;
        }
    }
    if(Value & 1 || dp[Value/2] < 0) puts("Can't be divided.\n");
    else puts("Can be divided.\n");
}

int main()
{
#ifdef Oj
    freopen("1014.in", "r", stdin);
#endif
    while(1) {
        Value = 0;
        for(int i=1; i<=6; ++i) cin >> a[i];
        for(int i=1; i<=6; ++i) Value += a[i]*i;
        if(Value == 0) break;
        solve();
    }
    return 0;
}