题目链接: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) 组合
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; bool dfs(int a, int b, int c, int d)
{
if ((a >= || !a) && (b >= || !b) && (c >= || !c) && (d >= || !d))// (1,1,1),(2,2,2), (3,3,3), (4,4,4) 的组合
return true;
if (a >= && b >= && c >= && d >= ) // (1, 2, 3, 4)
{
if (dfs(a-, b-, c-, d-))
return true;
}
if (a >= && b >= && c >= ) // (1, 2, 3)
{
if (dfs(a-, b-, c-, d))
return true;
}
if (b >= && c >= && d >= ) // (2, 3, 4)
{
if (dfs(a, b-, c-, d-))
return true;
}
return false;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
int T, ta, tb, tc, td;
while (scanf("%d", &T) != EOF)
{
while (T--)
{
scanf("%d%d%d%d", &ta, &tb, &tc, &td);
printf("%s\n", dfs(ta, tb, tc, td) ? "Yes" : "No");
}
return ;
}
}