title: 每日一题–取石子 date: 2019-10-26 20:41:10 tags:
算法每日一题67.取石头 (15分) C时间限制：3000 毫秒 | C内存限制：3000 Kb 题目内容： 有一堆石子，A，B两人轮流从中取出石子，每次取出的石子数目只能为1，3，7或8，最后一枚石子谁取到就是输方。 A,B两人都足够聪明，不会做出错误的判断。现给出一定数目的石子，A先取石子，计算A最终是输是赢，赢1表示，输用0表示.输入描述第一行为一个整数n(0< n <=100),表示玩n局，接下来n行每行有一个整数，表示对应的局提供的石子数（不大于10000）， 输出描述 编程输出A对应的n局是赢是输，赢输出1，输输出0. 输入样例 3 1 3 10 输出样例 0 0 1
#include <stdio.h> int main(){ int a[10001], b[101], res[101], n, i, j, max; scanf("%d", &n); a[9] = 1; a[8] = 1; a[7] = 1; a[6] = 1; a[5] = 0; a[4] = 1; a[3] = 0; a[2] = 1; a[1] = 0; for(i = 0; i < n; i++){ scanf("%d", &b[i]); } max = b[0]; for(i = 0; i < n; i++){ if(max < b[i]){ max = b[i]; } } // printf("%d\n", max); for(j = 10; j <= max; j++){ if(a[j - 1] == 0 || a[j - 3] == 0 || a[j - 7] == 0 || a[j - 8] == 0){ a[j] = 1; // printf("------"); }else{ a[j] = 0; } } for(i = 0; i < n; i++){ printf("%d\n", a[b[i]]); } }简单的动态规划问题，要解决大的问题，先解决小的问题。好比这题，当石头子的数量非常庞大时，我们就没有办法准确得到答案，但是当石子数量较少时，答案是显而易见的。因此，我们就要想办法把石子的数目往以得结果的数目上靠，一层一层往上走，逐步得到较大数目石子的答案。
万能引用
#include<bits/stdc++.h>