某 OJ 把这道题搬去做了 5311……名叫贞鱼(=_=)
Part1. 题面
有 n 个人和 k 辆车。人们排队上车,所以每辆车内是连续的一段人。已知第 i 个人和第 j 个人的厌恶值为 $y_{i,j}$,厌恶是相互的,即 $y_{i,j}=y_{j,i}$。
如果 i 和 j 在同一辆车里,就会产生 $y_{i,j}$ 的不愉快值($y_{i,j}$ 和 $y_{j,i}$ 只计算一次)。
数据规模:$1\le n\le4000,0\le y_{i,j}\le 9$,满足 $y_{i,j}=y_{j,i},y_{i,i}=0$。
Part2. 解析
Part2/1. 凸优化
发现是恰好 $k$ 辆车,(需要足够的脑洞)根据这一点可以向凸优化这方面思考。
显然车越多、总不愉快值越小,大概可以发现 $f(x)$ 表示 $n$ 个人有 $x$ 辆车时的最优解,$\left(x,f(x)\right)$ 成凸包。于是凸优化是正确的。
那么就是要二分斜率 $c$,求 $f’(x)=f(x)+cx$ 的最小值。即考虑每分一辆车,代价就额外增加 $c$。
根据这些,我们就不用管“恰好 $k$ 辆车”的限制,可以设计出 DP 状态 dp[x]
,表示前 x 个人划分完毕的最小总不愉快值,再维护 cnt[x]
为当 dp[x]
取得最小值时,最少 分了多少辆车(你也可以维护 最大,反正一定要知道自己是求的最大还是最小,不能随便)。
然后就可以得到一个非常显然的转移式子,也就是把第 j+1 到 i 个人分到一个车子里面,还要加上每辆车的附加值 c:
1
| dp[i] = min{ dp[j] + (sum[i][i] - sum[i][j] - sum[j][i] + sum[j][j])/2 + c }
|
> Tip
sum[a][b]
是 $\sum_{i=1}^a\sum_{j=1}^by_{i,j}$。
转移的时候还要统计一下 cnt[i]
。最后根据 cnt[n]
和 $k$ 的大小,更改 $c$ 的取值范围。
Part2/2. 决策单调性
然而我们发现,上面那种转移,对于每个 i,要枚举 j,也就是 $O(n^2)$ 的…… 然后再套上带权二分的 $O(\log_2w)$,变成了 $O(n^2\log_2w)$,好像卡不过 BZOJ 的机子(=_=)。
再观察 DP 结果(其实我是听 tiw dalao 讲的),可以发现 DP 决策是有单调性的!也就是说 dp[i]
的最优转移点 $d(i)$ 是与 $i$ 呈现非递减 关系的。所以再用决策单调性优化一下,就将枚举 j 的 $O(n)$ 降至二分 维护决策队列的 $O(\log_2n)$。
此时复杂度为 $O(n\log_2n\log_2w)$ 可以接受。
> Tip
关于决策单调性,比如下面这样:
1 2
| i = 1 2 3 4 ... d(i) = 0 1 1 2 ...
|
其中 d(i) 是 i 的最优转移点,对于这道题也就是说 dp[i]
的最小值为:
dp[i] = dp[d(i)]+(sum[i][i]-sum[d(i)][i]-sum[i][d(i)]+sum[d(i)][d(i)])/2+c
具体实现是用队列,存储对于每一个 i,哪一段区间是以它为最优决策点(可能为空)。当我们计算出 dp[i]
,因为决策具有单调性,就可以二分 i 的最左边的最优决策点。
具体看代码吧。
Part3. 源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
| #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=4000;
int n,m; int sum[N+3][N+3],cnt[N+3]; long long dp[N+3]; int que[N+3],inc[N+3],lef,rig;
int AddUp(int x1,int y1,int x2,int y2){return sum[x1][y1]-sum[x1][y2]-sum[x2][y1]+sum[x2][y2];} bool cmp(int las,int now,int finc){ long long resu_las=dp[las]+AddUp(finc,finc,las,las)/2, resu_now=dp[now]+AddUp(finc,finc,now,now)/2; int cnt_las=cnt[las]+1, cnt_now=cnt[now]+1; return resu_now<resu_las || (resu_now==resu_las && cnt_now<cnt_las); }
int BinarySearch(int incl,int incr,int lasque,int now){ int las=que[lasque]; if(!cmp(las,now,incr)) return 0; if(cmp(las,now,incl)){ rig=lasque; que[rig]=now; inc[rig]=n; return 1; } while(incl+1<incr){ int incm=(incl+incr)>>1; if(cmp(las,now,incm)) incr=incm; else incl=incm; } rig=lasque+1; inc[rig]=n; que[rig]=now; inc[lasque]=incr-1; return 2; }
bool Check(int add){ for(int i=1;i<=n;i++) dp[i]=(1ll<<60),cnt[i]=1e9; dp[0]=0; que[lef=rig=1]=0;inc[1]=n; for(int i=1;i<=n;i++){ while(inc[lef]<i) lef++; int j=que[lef]; if(i==inc[lef]) lef++; long long fdp=dp[j]+AddUp(i,i,j,j)/2+add; dp[i]=fdp; cnt[i]=cnt[j]+1; for(int j=rig;j>=lef;j--){ int resu=BinarySearch((j==lef? i+1:inc[j-1]+1),inc[j],j,i); if(resu==2 || resu==0) break; } } return cnt[n]<=m; } #define gc if(++ip==ie)fread(ip=buf,1,SZ,stdin) const int SZ=1<<19; char buf[SZ],*ie=buf+SZ,*ip=ie-1; inline int gi(){ gc;while(*ip<'-')gc; bool f=*ip=='-';if(f)gc; int x=*ip&15;gc; while(*ip>'-'){x*=10;x+=*ip&15;gc;} return f?-x:x; } int main(){ n=gi();m=gi(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ sum[i][j]=gi(); sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } int adl=-1e9,adr=1e9; while(adl+1<adr){ int adm=floor(adl/2.0+adr/2.0); if(Check(adm)) adr=adm; else adl=adm;
} Check(adr); printf("%lld\n",dp[n]-1ll*adr*m); return 0; }
|
The End
Thanks for reading!
BZOJ什么破机子……