问一道opj上面的题目，感觉很难

[pkuche...@gmail.com]

http://bailian.openjudge.cn/practice/4149/

第4149题，课程大作业

请问大家有什么思路吗，我没想到除了把所有情况全部考虑一遍然后取最小值以外的办法

[朱科萌]

这题有测试数据嘛...做了一个Wrong Answer，不知道原因...题目给的样例数据是过了...

T=int(input())
for t in range(T):
    N=int(input())
    course=[]
    for i in range(N):
        line=input().split()
        course.append([line[0],int(line[1]),int(line[2]),int(line[1])-int(line[2])])
    course.sort(key=lambda l:l[3])
    d=0
    ans=[]
    kf=0
    for c in course:
        d+=c[2]
        kf+=d-c[1] if d-c[1]>0 else 0
        ans.append(c[0])
    print(kf)
    print('\n'.join(ans))

在 2017年12月24日星期日 UTC+8下午10:39:59，pkuche...@gmail.com写道：

[Iru Cai]

我想过几种贪心的策略都不行，我可以给几组数据：

--
您收到此邮件是因为您订阅了Google网上论坛上的“cs101pku”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到cs101pku+unsubscribe@googlegroups.com。
要发帖到此群组，请发送电子邮件至cs101pku@googlegroups.com。
访问此群组：https://groups.google.com/group/cs101pku。
要查看更多选项，请访问https://groups.google.com/d/optout。

--

Please do not send me Microsoft Office/Apple iWork documents. Send OpenDocument instead! http://fsf.org/campaigns/opendocument/

[Iru Cai]

我想过几种贪心的策略都不行，我可以给几组数据，以下几组数据格式为 { (deadline, time), ...}

{ (3,2), (1,1) }
{ (3,1), (2,2) }
{ (1,10), (1,11) }
{ (10,10), (100, 1) }
{ (0, 100), (100, 1), (100, 1), (100, 1) }

我现在的想法是用A*算法搜索。

2017-12-25 12:54 GMT+08:00 朱科萌 <zhuk...@gmail.com>:

--
您收到此邮件是因为您订阅了Google网上论坛上的“cs101pku”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到cs101pku+unsubscribe@googlegroups.com。
要发帖到此群组，请发送电子邮件至cs101pku@googlegroups.com。
访问此群组：https://groups.google.com/group/cs101pku。
要查看更多选项，请访问https://groups.google.com/d/optout。

[Iru Cai]

我用A*算法过了 https://pastebin.com/WB8KSx83 不过时间和空间消耗比较大，看以前通过的有更高效的做法。
看这题的hint里面有用DP的，不知道怎么做。

--

My website: https://vimacs.lcpu.club

[pkuche...@gmail.com]

其实我到现在都没有想出来这个的数学思路是什么

在 2017年12月24日星期日 UTC+8下午10:39:59，pkuche...@gmail.com写道：

http://bailian.openjudge.cn/practice/4149/

[屠鑫明1600012130]

这道题要使用状压DP，难度超出了计概要求的

有兴趣的同学可以继续讨论

在 2017年12月24日星期日 UTC+8下午10:39:59，pkuche...@gmail.com写道：

http://bailian.openjudge.cn/practice/4149/