这道题让我还挺自豪的，因为我自己独立的把它写出来了（虽然经历了 timeover wronganswer），而且后来搜索网上的一些解答，貌似和他们的想法都不是很像的样子。而且，通过的数据貌似还挺好 0ms
Problem: 1014 User: yisnesia
Memory: 720K Time: 0MS
Language: G++ Result: Accepted这让我挺欣慰的。看到网上很多人都说到了 dp 的方法，我这里好像没有用唉，我用的差不多就是基本的搜索算法，然后用到了一个比较省时的启发：从 6->1 逆序搜索，并且一次性取尽量多这个价值的大理石 (如果一次仅仅取一个会超时的哦)。
#include <iostream>
#include <cstdio>
/*
* http://poj.org/problem?id=1014
*
* 这道题我把它认为是搜索题
* 要搜索的内容是 两个大小一样的分组
* 那么我只需要找到一个大小恰好为总和一半的分组就达到目的了
*
* @author: aisensiy(http://weibo.com/alistapart)
*/
using namespace std;
int marbles[6];
bool search(int cur, int half) {
// 这里引入了贪婪的思想，要从大的开始找，并且一次取尽量多
for(int i=5; i>=0; i--) {
if(!marbles[i]) continue;
// 尽量多就是满足 或者 取尽
int num = (half-cur) / (i+1) > marbles[i] ? marbles[i] : (half-cur) / (i+1);
if(num == 0) continue;
marbles[i] -= num;
if(cur + (i+1) * num == half) return true;
else if(search(cur + (i+1) * num, half)) return true;
marbles[i] += num;
}
return false;
}
int main() {
int counter=1, sum=0;
while(1) {
for(int i=0; i<6; i++) {
cin>>marbles[i];
sum += (i+1) * marbles[i];
}
if(!sum) break;
// 这里有一个小 trick，如果总和本来就是计数
// 则一定不能分成一样的两堆
if(sum % 2 != 0 || !search(0, sum/2)) {
printf("Collection #%d:\n"
"%s\n\n", counter, "Can't be divided.");
} else {
printf("Collection #%d:\n"
"%s\n\n", counter, "Can be divided.");
}
counter++;
sum = 0;
}
return 0;
}