[POJ 1014] Dividing【DFS】
Problem:
Time Limit: 1000MS | Memory Limit: 10000K |
Description
Input
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.
Output
Output a blank line after each test case.
Sample Input
1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0
Sample Output
Collection #1: Can't be divided. Collection #2: Can be divided.
Source
Solution:
这一题本来是多重背包的模板题,乍一看 DFS 会 TLE。但是 DFS 有一个非常有效的可行性剪枝,可以将时间复杂度降到与多重背包相近。
首先判断价值总和是否为偶数,如果不是,直接输出 "Can't be divided."。
DFS 时从大到小枚举,可以更快地找到答案。
每当取走某一价值的大理石的尝试失败时,无需回溯。因为若回溯,在后续尝试中还会取到同一块大理石,肯定会再次失败,不符合可行性。可以视为将该大理石给对方。
Code: O(玄学) [320K, 0MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int T = 0, n[7], ave; inline bool getCollection(){ for(register int i = 1; i <= 6; i++) if(scanf("%d", n + i) == EOF) return 0; return 1; } inline bool DFS(int tot){ if(tot == ave) return 1; for(register int i = 6; i >= 1; i--) if(n[i] && tot + i <= ave){ n[i]--; if(DFS(tot + i)) return 1; // Feasibility pruning: not to backdate the n[i], or the program will receive TLE /* Reason: When the attempt of taking value i fails, we consider giving this value i to the other person, or we must fail again. */ } return 0; } int main(){ while(getCollection() && (n[1] != 0 || n[2] != 0 || n[3] != 0 || n[4] != 0 || n[5] != 0 || n[6] != 0)){ printf("Collection #%d:\n", ++T); ave = n[1] + 2 * n[2] + 3 * n[3] + 4 * n[4] + 5 * n[5] + 6 * n[6]; if(ave & 1){ puts("Can't be divided.\n"); continue; } ave >>= 1; if(DFS(0)) puts("Can be divided.\n"); else puts("Can't be divided.\n"); } return 0; }
发表评论