P6462补刀

灵光一现,突然就做出来了

正好写一下思路过程

一开始寻思是个数论的问题,貌似需要用到扩展欧几里得,不管那么多,直接写上,接着不断缝缝补补修修改改,此处省略一小时....

做不出来....好难受

星期天,无聊,做个题..

突然,不对啊

这个题实际上不就是我当前打还是不打的一个选择吗?

这个打和不打怎么这么熟悉???

嗯??打还是不打??我这不是能用深搜吗!!!分类深搜讨论就行啊!!!

思路到这就很清晰了,就是dfs深搜分类讨论

注意两点

1.最开始的那一下也要分类讨论打还是不打,因为我们后面都是默认塔先打

2.不需要恰好打死,打的血量>=当前血量即可,而且是塔先打,然后我再讨论当前打还是不打

这个打还是不打,和选还是不选是真的很像,中间有段时间我还在想是不是动态规划,但想了一下是真想不明白状态和属性,就换成了搜索,dfs还是挺好用的,就是讨论,中间还有点细节点,不过也很好想到

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define endl '\n'
#define int int64_t
using namespace std;
int dfs(int h, int x, int y) {//打还是不打  默认是先塔打   不需要恰好击杀,<= 0就代表了击杀if (h <= x) return 0;h -= x;if (h <= y) return 1;int nd = dfs(h, x, y);if (nd) return 1;int d = dfs(h - y, x, y);if (d) return 1;return 0;
}
void solve() {int h, x, y,k,m; cin >> h >> x >> y;if (!x && y) { cout << "Yes" << endl; return; }if (!y) { cout << "No" << endl; return; }//第一下打还是不打//打if (h <= y) { cout << "Yes" << endl; return; }int fd = dfs(h - y, x, y);if (fd) { cout << "Yes" << endl; return; }int sd = dfs(h, x, y);if (sd) { cout << "Yes" << endl; return; }cout << "No" << endl;
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) {solve();}return 0;
}