网站的公告轮播效果怎么做,WordPress手机端底部悬浮窗,网站配色方案橙色,西乡专业建站P - 节拍 Zty是一个总是充满热情的人。他想解决世界上各种困难的ACM问题。而且他有一个习惯#xff0c;他不喜欢解决 一个比他已经解决的问题容易的问题。现在一芬飞给他n个难度问题#xff0c;在解决另一个问题后告诉他解决的相对时间。 你应该帮助zty找到一个解决问题的顺序…P - 节拍 Zty是一个总是充满热情的人。他想解决世界上各种困难的ACM问题。而且他有一个习惯他不喜欢解决 一个比他已经解决的问题容易的问题。现在一芬飞给他n个难度问题在解决另一个问题后告诉他解决的相对时间。 你应该帮助zty找到一个解决问题的顺序以解决更困难的问题。 您可以确定 zty 首先通过花费 0 分钟来解决问题 0。Zty总是选择成本更多或时间相等的问题来解决。 输入 输入包含多个测试用例。 每个测试用例包括第一个整数 n 2 n 15.表示问题的数量。 比 n 行每行包括 n 个整数 Tij 0Tij10i 的行和 j 的整数 Tij 表示在解决问题 i 后将花费 Tij 分钟来解决问题 j。 输出 对于每个测试用例输出zty 可以解决的最大问题数。 样本 输入输出 3
0 0 0
1 0 1
1 0 0
3
0 2 2
1 0 1
1 1 0
5
0 1 2 3 1
0 0 2 3 1
0 0 0 3 1
0 0 0 0 2
0 0 0 0 03
2
4提示 提示示例一正如我们所知zty 总是通过花费 0 分钟来解决问题 0。 所以在解决了问题 0 之后他可以选择问题 1 和问题 2因为 T01 0 和 T020。 但是如果 zty 选择解决问题 1他就无法解决问题 2因为 T12 T01。 所以 zty 可以选择解决问题 2 秒而不是解决问题 1。 思路 利用dfs每次搜索时比较当前问题解决时间若大于当前时间则更新并标记为经过并进入下一次搜索。 代码 #define _CRT_SECURE_NO_WARNINGS 1
#include iostream
#include algorithm
#include queue
#includemap
#include cstring
int a[20][20], vis[20];
int ans, cnt, n;
using namespace std;
void dfs(int cnt, int i, int mmax)
{if (cnt ans){ans cnt;}vis[i] 1;for (int j 0; j n; j){if (!vis[j] a[i][j] mmax){dfs(cnt 1, j, a[i][j]);}}vis[i] 0;
}
int main()
{while (cin n){for (int i 0; i n; i){for (int j 0; j n; j){cin a[i][j];}}ans 0;dfs(1, 0, 0);cout ans endl;}return 0;
}