城堡店面挂

KyleZhao

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

分享下今早新鲜城堡店面面经，求教怎么做。
给一个n*n matrix，从每一行和每一列取且仅取一个数求和，最大的和是多少？
Exa

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

on...
貌似是可以用Hungarian algorithm？

来自APP · 2022-3-30 00:53:08

楼主面的是哪个组啊

1311553603

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-XPZOF *2022-4-12 04:32:22* · 2022-4-12 04:32:22

本帖最后由匿名于 2022-4-11 16:36 编辑

貌似可以用DP来解：让dp[x][y]代表前X行不包括Y列的最大值（X数之和）。X从1到n迭代。

thorax

这个似乎和8皇后是一样的？

匿名用户-DZJTV *2022-4-18 10:43:47* · 2022-4-18 10:43:47

暴力硬搜+剪枝就可以了

xiana406

这不是典型的dp吗？

黄色战神 · 2022-10-10 02:51:37

匿名用户发表于 2022-4-11 13:32
貌似可以用DP来解：让dp[x][y]代表前X行不包括Y列的最大值（X数之和）。X从1到n迭代。

请问关系式是什么？

黄色战神 · 2022-10-10 02:51:48

xiana406 发表于 2022-7-19 09:56
这不是典型的dp吗？

来说说怎么dp请问关系式是什么？

张欣 · 2022-11-13 11:53:18

xiana406 发表于 2022-7-19 08:56
这不是典型的dp吗？

这个应该不太符合子问题性质吧，好像不太能用DP