 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
关于这题,菜鸟的想法..In Reply To:Re:Towards Identity Anonymization on Graphs Posted by:Rainer at 2009-01-02 11:07:21 dp,由于是限定了非递减,故dp方程为dp[i] = min{dp[j] + sum[i,j-1] - a[i]*(j - 1)}
{i + k<=j<=n + 1};
很明显,n^2的复杂度,而是否可以用斜率优化????对于斜率优化,菜鸟本来就理解不深,所以没能写出斜率方程..但本题的复杂度如果能用斜率或单调队列优化等,应该可降到线性的,只是没想出,从去年卡到今年的题,灌水水一个..
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
