首页 > 代码库 > BestCoder22 1002.NPY and arithmetic progression(hdu 5143) 解题报告
BestCoder22 1002.NPY and arithmetic progression(hdu 5143) 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5143
题目意思：给出 1, 2, 3, 4 的数量，分别为a1, a2, a3, a4，问是否在每个数只使用一次的前提下，分成若干部分，每部分数的长度 >= 3且满足是等差数列。可以的话输出 Yes ，否则 No 。
比赛的时候过了pretest，那个开心啊～～然后跟 XX 兽讨论了之后，才发现自己理解错了题目= =
要用到深搜，问组合嘛～～组合就是有可能是(1, 2, 3, 4)、(1, 2, 3)、(2, 3, 4) 与 cnt[1] >= 3 || cnt[1] == 0 { (1, 1, 1), (0)} ，cnt[2] >= 3 || cnt[2] == 0，cnt[3] >= 3 || cnt[3] == 0， cnt[4] >= 3 || cnt[4] == 0 的组合。
cnt[i] 表示数字 i 的数量有cnt[i]个。其实总共有16种情况。
0 0 0 0， 0 0 0 3， 0 0 3 0， 0 0 3 3
0 3 0 0， 0 3 0 3， 0 3 3 0， 0 3 3 3
3 0 0 0， 3 0 0 3， 3 0 3 0， 3 0 3 3
3 3 0 0， 3 3 0 3， 3 3 3 0， 3 3 3 3
注意：填 3 的那些位置实际上 >= 3 都符合条件的。然后跟(1, 2, 3, 4)、(1, 2, 3)、(2, 3, 4) 组合
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 bool dfs(int a, int b, int c, int d) 8 { 9 if ((a >= 3 || !a) && (b >= 3 || !b) && (c >= 3 || !c) && (d >= 3 || !d))// (1,1,1)，(2,2,2), (3,3,3), (4,4,4) 的组合10 return true;11 if (a >= 1 && b >= 1 && c >= 1 && d >= 1) // (1, 2, 3, 4)12 {13 if (dfs(a-1, b-1, c-1, d-1))14 return true;15 }16 if (a >= 1 && b >= 1 && c >= 1) // (1, 2, 3)17 {18 if (dfs(a-1, b-1, c-1, d))19 return true;20 }21 if (b >= 1 && c >= 1 && d >= 1) // (2, 3, 4)22 {23 if (dfs(a, b-1, c-1, d-1))24 return true;25 }26 return false;27 }28 29 int main()30 {31 #ifndef ONLINE_JUDGE32 freopen("in.txt", "r", stdin);33 #endif // ONLINE_JUDGE34 int T, ta, tb, tc, td;35 while (scanf("%d", &T) != EOF)36 {37 while (T--)38 {39 scanf("%d%d%d%d", &ta, &tb, &tc, &td);40 printf("%s\n", dfs(ta, tb, tc, td) ? "Yes" : "No");41 }42 return 0;43 }44 }
BestCoder22 1002.NPY and arithmetic progression(hdu 5143) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。