2012-C18-team3

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
今天我们队伍发挥的一般，有2道题都不会做……

重点来说说G题，最优的解法应该是马甲的n^2，我来说说我们的n^2*k。当时肥羊学长认为这是过不了的，过了也是运气好才卡过的，其实不是这样的，因为k只有6000，
当你已经帮助了j个人的时候，设你帮助他们的时间是a1,a2,……,aj,那么你消耗的代价是a1*j+a2*（j-1）+……+aj*1，这个数最小是多少呢，j*(j+1)/2，所以
对于一个[i][j]，他对应的k最多就是max(6000-j*(j+1)/2+1,0)(0<=j<=i)个状态，粗略算了一下大概<10^8，还是应该能过的……

虽然这道题用这种解法不是很优美，但是我觉得这种思想还是很值得借鉴的，很多时候算法的复杂度并不像我们一眼看上去那么高，还是需要我们去仔细分析的。

--Flandre_Scarlet
}}}


{{{
补充一下~G题这种题的做法可以总结一下，其实训练的时候，已经做过3道类似的题目了：
某场训练的送pizza，天津网络赛的1006，这次的G题，都是利用“重叠计算”（大概是这个意思吧）的性质，来构造dp递推式，以后再遇到这种模型应该举一反三吧

然后D题我很早就想写，但一直没有人AC担心题目有问题，我们又在乱搞E，就拖了很久直到最后半小时数据范围被更正后才开始写
虽然现场赛出现这个情况的概率比较小，但以后遇到这种妥妥的题目，还是应该果断上去写一下
然后就是学长们的英语阅读需要提升啊。。D题怎么可能读不懂呢，我还是觉得原因在于没有用心去读，再复杂的题目，借助google翻译都应该读懂的

所以还是那个问题，不要因为这是模拟训练，遇到比较长比较复杂的题目就不想深入读下去，一定要摆正心态，如果是正式赛，我们都没有读D题，那岂不是就悲剧了T-T
--大肥羊
}}}

{{{
补充说明：不知道为什么，到了比赛后期，我就会读不懂题目了，特别是那种比较长的题目，而且有些单词不太认识的话。到了比赛后期，满脑子都在想题，看着那些单词，
每个词都知道意思，但就是串不起来连成一个句子。难道是我的大脑内存不够用了，555555……

--Flandre_Scarlet
}}}

今天我们队伍发挥的一般，有2道题都不会做……
重点来说说G题，最优的解法应该是马甲的n^2，我来说说我们的n^2*k。当时肥羊学长认为这是过不了的，过了也是运气好才卡过的，其实不是这样的，因为k只有6000，
当你已经帮助了j个人的时候，设你帮助他们的时间是a1,a2,……,aj,那么你消耗的代价是a1*j+a2*（j-1）+……+aj*1，这个数最小是多少呢，j*(j+1)/2，所以
对于一个[i][j]，他对应的k最多就是max(6000-j*(j+1)/2+1,0)(0<=j<=i)个状态，粗略算了一下大概<10^8，还是应该能过的……
虽然这道题用这种解法不是很优美，但是我觉得这种思想还是很值得借鉴的，很多时候算法的复杂度并不像我们一眼看上去那么高，还是需要我们去仔细分析的。
--Flandre_Scarlet

补充一下~G题这种题的做法可以总结一下，其实训练的时候，已经做过3道类似的题目了：
某场训练的送pizza，天津网络赛的1006，这次的G题，都是利用“重叠计算”（大概是这个意思吧）的性质，来构造dp递推式，以后再遇到这种模型应该举一反三吧
然后D题我很早就想写，但一直没有人AC担心题目有问题，我们又在乱搞E，就拖了很久直到最后半小时数据范围被更正后才开始写
虽然现场赛出现这个情况的概率比较小，但以后遇到这种妥妥的题目，还是应该果断上去写一下
然后就是学长们的英语阅读需要提升啊。。D题怎么可能读不懂呢，我还是觉得原因在于没有用心去读，再复杂的题目，借助google翻译都应该读懂的
所以还是那个问题，不要因为这是模拟训练，遇到比较长比较复杂的题目就不想深入读下去，一定要摆正心态，如果是正式赛，我们都没有读D题，那岂不是就悲剧了T-T
--大肥羊

补充说明：不知道为什么，到了比赛后期，我就会读不懂题目了，特别是那种比较长的题目，而且有些单词不太认识的话。到了比赛后期，满脑子都在想题，看着那些单词，
每个词都知道意思，但就是串不起来连成一个句子。难道是我的大脑内存不够用了，555555……
--Flandre_Scarlet