TopCoder SRM 658 Div1
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------------------
Hard是个构造题就不想做（其实是不会做）
话说这场是构造场吗...两道构造题...
---------------------------------------------------------------
Easy:
题意是给你一个二维数组x,x[i][j]表示i到j的距离是奇数还是偶数,让你构造一棵树,满足x
选一个点当根,其他点如果跟他的距离是奇数,就放在第一层,偶数就放在第二层
再验证一下x合不合法
没了..
---------------------------------------------------------------
Medium:
题意是你有n个敌人,第i个人有x[i]的血量,每次攻击可以打三个人,第一个人掉9滴血,第二个人掉3滴血,第三个人掉1滴血,三个人不能相同,问至少多少次攻击把所有人打死,n<=20,x[i]<=60,样例给了提示答案不会超过93
一颗赛艇啊...
看了题解的提示说这道题是二分答案+DP才想出来的..
首先二分答案攻击次数
假设当前次数是k
考虑怎么验证,现在相当于得到了k个9,k个3,k个1,把他们分配给所有人,要求每个人得到的和>=他的血量,且得到的数的个数<=k(否则就会有一次攻击打到两个人的情况,如果满足了这个就一定可以构造出没有一次攻击打到两个人的情况的攻击序列)
然后就可以DP辣
设f[i][j][k][l]表示前i个人,还剩j个9,k个3,l个1,转移:
枚举u9,u3,u1,满足9*u9+3*u3+u1 >= x[i],u9+u3+u1<=k分别表示给这个人分配几个9,3,1
若f[i][j][k][l]=max{f[i][j+u9][k+u3][l+u1]} (这里把true视为1,把false视为0)
然后...然后就发现T了
然后优化一下,勉强卡过去了
用了这几个优化:不枚举u1,而是用max{x[i]-3*u3-9*u9,0}来算出u1
当3*u3+9*u9 > x[i]时,跳出枚举u3的循环
当9*u9 > x[i]时,跳出枚举u9的循环
用__attribute__(optimaze("O2"))强行开了O2
嗯...就这么卡过去了...最大的点1.995秒...
---------------------------------------------------------------
评论 (0)
