甘谷县建设局网站,网站建设保密协议,2345网址导航大全,晋城建设局网站本来不想用递归做的#xff0c;最后还是用了
题目如下#xff1a;
洪尼玛有 n 块长度不同的木板#xff0c;他想用这些木板拼成一个等边三角形的围栏#xff0c;好将他的草泥马养在这个围栏里面。现在#xff0c;给你这 n 块木板的长度#xff0c;洪尼玛想知道他能否拼…本来不想用递归做的最后还是用了
题目如下
洪尼玛有 n 块长度不同的木板他想用这些木板拼成一个等边三角形的围栏好将他的草泥马养在这个围栏里面。现在给你这 n 块木板的长度洪尼玛想知道他能否拼成这个围栏要求n 块木板都得用上。 输入格式: 第一行为一个正整数 T 表示有 T 组测试数据。 对于每组测试数据第一行为一个正整数 n 表示木板个数第二行包含 n 个正整数表示每块木板的长度。 对于 60% 的数据1≤T≤53≤n≤5每块木板长度大于等于 1 小于等于 100。 对于 100% 的数据1≤T≤53≤n≤10 每块木板长度大于等于 1 小于等于 100 。 输出格式: 对于每一组测试数据输出一行。 如果能拼成围栏输出 Yes 否则输出 No 。 输入样例: 2 4 1 2 3 4 4 1 2 3 3 高中同学问的
最后是用了递归受不了本来以为找到了一个优解最后是根本不行
还是用了递归
代码如下
#includestdio.h
void sort(int num[], int n);
int dg(int num[], int idx, int sum);
int tmp, occ[10];int main(void)
{int T, n;int plank[10];scanf(%d, T);//开始输入并处理for(int x 0; x T; x){scanf(%d, n);for(int i 0; i n; i){scanf(%d, plank[i]);tmp plank[i];}if(tmp % 3){printf(No);break;}tmp / 3;//排序sort(plank, n);//判断行不行if(dg(plank, n - 1, plank[n - 1]) dg(plank, n - 2, plank[n - 2]) dg(plank, n - 3, plank[n - 3]))printf(Yes);elseprintf(No);}
}
void sort(int num[], int n)
{for(int i 0; i n - 1; i)for(int j i 1; j n; j)if(num[i] num[j])num[i] ^ num[j] ^ num[i] ^ num[j];return;
}
int dg(int num[], int idx, int sum)
{if(sum tmp || occ[idx]) return 0;else if(sum tmp) {occ[idx] 1; return 1;}occ[idx] 1;for(int i idx - 1; i 0; i--)if(dg(num, i, sum num[i]))return 1;return 0;
}
